题解 | #连续子数组最大和#

题目链接

连续子数组最大和

题目描述

小红拿到了一个数组，她可以执行最多一次操作：选择数组中的一个元素，将其值修改为 $x$ 。

请你计算，在执行最多一次修改操作后，该数组的“连续子数组最大和”最大能达到多少。

思路分析

这是一个经典动态规划问题“连续子数组最大和”（Kadane's Algorithm）的变种。我们可以通过扩展 DP 状态来处理“最多一次修改”这个额外的维度。

1. 状态定义

我们定义两个 DP 状态，分别表示在遍历到数组第 $i$ 个元素时，以该元素结尾的连续子数组的最大和：

dp0：表示没有进行过修改操作的情况下，以当前元素结尾的连续子数组的最大和。
dp1：表示已经进行过一次修改操作的情况下，以当前元素结尾的连续子数组的最大和。

同时，我们需要一个全局变量 max_sum 来记录整个过程中的最大值。

2. 状态转移

当我们遍历到数组的第 $i$ 个元素 a[i] 时，我们更新 dp0 和 dp1：

更新 dp0 (未修改)
- 以 a[i] 结尾且未修改的子数组，要么是 a[i] 自身，要么是 a[i] 接在之前未修改的子数组之后。
- 转移方程: dp0 = max(a[i], dp0 + a[i])
更新 dp1 (已修改)
- 以 a[i] 结尾且已修改的子数组，其“修改”操作有两种可能：
  
  a. 修改就发生在 a[i]：我们将 a[i] 的值视为 $x$ 。这个新的子数组要么是 $x$ 自身，要么是 x 接在之前未修改的子数组（以 a[i-1] 结尾）之后。这部分的最大和是 max(x, dp0_before_update + x)。（注意这里用的是更新前的 dp0）。
  
  b. 修改发生在 a[i] 之前：这意味着 a[i] 保持原值，并接在之前已修改的子数组（以 a[i-1] 结尾）之后。这部分的最大和是 dp1 + a[i]。
- 我们将这两种可能取最大值。
- 转移方程: dp1 = max(max(x, dp0_before_update + x), dp1 + a[i])

3. 最终答案

在遍历的每一步，我们都需要用当前的 dp0 和 dp1 来更新全局的 max_sum。

max_sum = max(max_sum, dp0)
max_sum = max(max_sum, dp1)

初始时，max_sum 应该被初始化为一个足够小的负数。遍历结束后，max_sum 就是最终的答案。这个答案已经包含了“不修改任何元素”的情况（因为 dp0 的更新过程就是标准的 Kadane 算法）。

由于 dp 的状态只依赖于前一个状态，我们可以用两个变量代替 DP 数组，将空间复杂度优化到 $O(1)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long x;
    cin >> n >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long dp0 = 0;
    long long dp1 = 0;
    long long max_sum = -2e18; // 一个足够小的数

    for (int i = 0; i < n; ++i) {
        long long prev_dp0 = dp0;
        
        // 先更新dp1，因为它依赖于上一轮的dp0
        // 修改发生在a[i] vs 修改发生在a[i]之前
        dp1 = max({(long long)a[i] + dp1, x, x + prev_dp0});

        // 再更新dp0
        dp0 = max((long long)a[i], a[i] + dp0);

        max_sum = max({max_sum, dp0, dp1});
    }

    cout << max_sum << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long x = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        long dp0 = 0;
        long dp1 = 0;
        long maxSum = Long.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            long prevDp0 = dp0;
            
            // 先更新dp1
            long modifiedAtI = Math.max(x, x + prevDp0);
            long modifiedBeforeI = a[i] + dp1;
            dp1 = Math.max(modifiedAtI, modifiedBeforeI);

            // 再更新dp0
            dp0 = Math.max(a[i], a[i] + dp0);

            maxSum = Math.max(maxSum, Math.max(dp0, dp1));
        }

        System.out.println(maxSum);
    }
}

import sys

def solve():
    n, x = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    dp0 = 0
    dp1 = 0
    max_sum = -float('inf')

    for val in a:
        prev_dp0 = dp0
        
        # 先更新dp1
        modified_at_i = max(x, x + prev_dp0)
        modified_before_i = val + dp1
        dp1 = max(modified_at_i, modified_before_i)

        # 再更新dp0
        dp0 = max(val, val + dp0)
        
        max_sum = max(max_sum, dp0, dp1)

    print(max_sum)

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划
时间复杂度： $O(N)$ 。
- 我们只需要对输入的数组进行一次完整的遍历。
空间复杂度： $O(1)$ 。
- 由于 DP 状态只依赖于前一个状态，我们使用了滚动变量的方式，只需要常数级别的额外空间。