5900: 【DP】小红书2023秋招提前批-连续子数组最大和
金币值：
1
时间限制：10.000 s
内存限制：512 M
正确：22
提交：30
正确率：73.33% 命题人：
题目描述
小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？
输入格式
第一行输入一个正整数t，代表询问次数。
对于每次询问，输入两行：
第一行输入两个整数n和x。代表数组的大小，以及小红可以修改成的元素。
第二行输入n个正整数a_i，代表小红每次询问拿到的数组。
1 ≤ t ≤ 100000
1 ≤ n ≤ 200000
-10^9 ≤ x, a_i ≤ 10^9
每组所有询问的n的和不超过200000。
输出格式
输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。
输入样例 复制
3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1输出样例 复制
15
-2
15提示
第一组询问，修改第二个数。
第二组询问，不进行任何修改。
第三组询问，修改第三个数。