连续子数组最大和

[题目链接](https://www.nowcoder.com/practice/3e35a0679ec94df69e7db3b6e6bbf8fd)

思路

本题是经典"最大子数组和"（Kadane 算法）的变体：允许最多将一个元素替换为给定值 $p$ ，求连续子数组的最大和。

状态定义

用两个变量滚动更新即可，无需开数组：

$dp0$ ：以当前位置结尾的最大子数组和，未做任何替换；
$dp1$ ：以当前位置结尾的最大子数组和，恰好替换了一个元素。

转移方程

对于位置 $i$ ：

$ $dp0_i = \max(a_i,\; dp0_{i-1} + a_i)$ $

含义与标准 Kadane 完全一致——要么从当前位置重新开始，要么延续之前的子数组。

$ $dp1_i = \max(p,\; dp0_{i-1} + p,\; dp1_{i-1} + a_i)$ $

三种情况分别对应：

只选当前位置，且把它替换为 $p$ ：子数组长度为 1；
把当前位置替换为 $p$ ，接在之前未替换的子数组后面：之前没用过替换机会，在这里用掉；
保留当前位置，接在之前已替换过的子数组后面：替换机会已经在前面用掉了，当前位置保持原值。

答案

全局答案取所有位置的 $\max(dp0_i, dp1_i)$ 的最大值，因为可以选择不替换（取 $dp0$ ）或替换一个（取 $dp1$ ）。

初始化

$ $dp0 = a_0, \quad dp1 = p$ $

$dp1$ 初始为 $p$ ，表示把第一个元素替换为 $p$ 。

样例演示

第一组： $a = [5, -1, -5, -3, 2]$ ， $p = 10$ 。

把 $a_2 = -5$ 替换为 $10$ ，子数组 $[5, -1, 10] \to$ 和为 $14$ ？不，最优是把 $a_1 = -1$ 替换为 $10$ ，子数组 $[5, 10] = 15$ 。DP 过程会自动找到这个最优方案。

复杂度

时间复杂度： $O(n)$ ，每组询问线性扫描一次。
空间复杂度： $O(n)$ ，用于存储输入数组（DP 本身只用 $O(1)$ 额外空间）。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        long long p;
        scanf("%d%lld",&n,&p);
        vector<long long> a(n);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        long long dp0=a[0], dp1=p;
        long long ans=max(dp0,dp1);
        for(int i=1;i<n;i++){
            long long ndp0=max(a[i], dp0+a[i]);
            long long ndp1=max({p, dp0+p, dp1+a[i]});
            dp0=ndp0;
            dp1=ndp1;
            ans=max({ans,dp0,dp1});
        }
        printf("%lld\n",ans);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long p = Long.parseLong(st.nextToken());
            st = new StringTokenizer(br.readLine());
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
            long dp0 = a[0], dp1 = p;
            long ans = Math.max(dp0, dp1);
            for (int i = 1; i < n; i++) {
                long ndp0 = Math.max(a[i], dp0 + a[i]);
                long ndp1 = Math.max(p, Math.max(dp0 + p, dp1 + a[i]));
                dp0 = ndp0;
                dp1 = ndp1;
                ans = Math.max(ans, Math.max(dp0, dp1));
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

T = int(input())
out = []
for _ in range(T):
    line1 = input().split()
    n, p = int(line1[0]), int(line1[1])
    a = list(map(int, input().split()))
    dp0 = a[0]
    dp1 = p
    ans = max(dp0, dp1)
    for i in range(1, n):
        ndp0 = max(a[i], dp0 + a[i])
        ndp1 = max(p, dp0 + p, dp1 + a[i])
        dp0 = ndp0
        dp1 = ndp1
        if dp0 > ans:
            ans = dp0
        if dp1 > ans:
            ans = dp1
    out.append(ans)
print('\n'.join(map(str, out)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    let T = parseInt(lines[idx++]);
    const res = [];
    while (T-- > 0) {
        const parts = lines[idx++].split(' ');
        const n = parseInt(parts[0]);
        const p = BigInt(parts[1]);
        const a = lines[idx++].split(' ').map(x => BigInt(x));
        let dp0 = a[0], dp1 = p;
        let ans = dp0 > dp1 ? dp0 : dp1;
        for (let i = 1; i < n; i++) {
            const ndp0 = a[i] > dp0 + a[i] ? a[i] : dp0 + a[i];
            let ndp1 = p;
            if (dp0 + p > ndp1) ndp1 = dp0 + p;
            if (dp1 + a[i] > ndp1) ndp1 = dp1 + a[i];
            dp0 = ndp0;
            dp1 = ndp1;
            if (dp0 > ans) ans = dp0;
            if (dp1 > ans) ans = dp1;
        }
        res.push(ans.toString());
    }
    console.log(res.join('\n'));
});