连续子数组最大和

import java.util.Scanner;

// dp[i][0/1]：0表示未修改 1表示修改1次
// 状态机DP：先学好买股票
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = in.nextInt(), x = in.nextInt();
            long[][] dp = new long[n + 1][2];
            long max = Long.MIN_VALUE;
            for (int i = 1; i <= n; i++) {
                int a = in.nextInt();
                // 未修改：普通的连续子数组最大和
                dp[i][0] = Math.max(dp[i - 1][0], 0) + a; 
                // 修改1次：沿用上个数修改1次的 &nbs***bsp;使用上个数未修改的+当前数修改为x
                dp[i][1] = Math.max(dp[i - 1][1] + a, Math.max(dp[i - 1][0], 0) + x);
               
                max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
            }
            sb.append(max).append('\n');
        }
        System.out.print(sb.toString());
    }
}