7月23日：小红书提前批笔试第三题

没投小红书提前批，下来做了下第三题（第一题签到题；第二题没看，大家说看不懂题意），时间复杂度 O(n)，塔子哥 OJ 上提交 AC

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        while (t-- > 0) {
            int n = cin.nextInt();
            long v = cin.nextLong();
            long[] nums = new long[n];
            for (int i = 0; i < n; i++) {
                nums[i] = cin.nextLong();
            }

            // dp[0][j]: 不强化 nums[0] ~ nums[j] 的子序和
            // dp[1][j]: 强化 nums[0] ~ nums[j] 中的某一个的子序和，又分为强化 nums[j] 和 不强化 nums[j]
            long[][] dp = new long[2][n];
            dp[0][0] = nums[0];
            dp[1][0] = v;
            long maxSum = Math.max(dp[0][0], dp[1][0]);
            for (int j = 1; j < n; j++) {
                // 不强化时 nums[0] ~ nums[j] 的子序和
                dp[0][j] = Math.max(dp[0][j - 1] + nums[j], nums[j]);
                // 强化 nums[j]：Math.max(dp[0][j - 1] + v, v)
                // 不强化 nums[j]，强化 nums[0] ~ nums[j-1] 中的某一个，即 dp[1][j - 1]：dp[1][j - 1] + nums[j]
                dp[1][j] = Math.max(Math.max(dp[0][j - 1] + v, v), dp[1][j - 1] + nums[j]);
                maxSum = Math.max(maxSum, Math.max(dp[0][j], dp[1][j]));
            }
            System.out.println(maxSum);
        }
    }
}