连续子数组最大和

[编程题]连续子数组最大和

热度指数：11 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为 $x$ 。小红想知道，最终的连续子数组最大和最大是多少？

输入描述:

第一行输入一个正整数，代表询问次数。
对于每次询问，输入两行：
第一行输入两个正整数和。代表数组的大小，以及小红可以修改成的元素。
第二行输入个正整数，代表小红拿到的数组。



每组所有询问的的和不超过200000。

输出描述:

输出行，每行输出一个整数，代表连续子数组的最大和。

示例1

输入

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

输出

15
-2
15

说明

第一组询问，修改第二个数。
第二组询问，不进行任何修改。
第三组询问，修改第三个数。

算法知识视频讲解

Java

Sen🍓🍀

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());
    }
}

发表于 2025-07-08 20:12:25 回复(0)