首页 > 试题广场 >

连续子数组最大和

[编程题]连续子数组最大和
  • 热度指数：11 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入描述:
第一行输入一个正整数t，代表询问次数。
对于每次询问，输入两行：
第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。
第二行输入n个正整数a_i，代表小红拿到的数组。
1\leq t\leq 100000
1\leq n \leq 200000
-10^9 \leq x ,a_i\leq 10^9
每组所有询问的n的和不超过200000。


输出描述:
输出t行，每行输出一个整数，代表连续子数组的最大和。
示例1

输入

3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1

输出

15
-2
15

说明

第一组询问，修改第二个数。
第二组询问，不进行任何修改。
第三组询问，修改第三个数。
算法知识视频讲解
开通博客

暂无题解

问题信息

难度：
1条回答 4浏览

热门推荐

相关试题

连续子数组最大和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号