最大子段和

题意

给定一个整数序列，求连续且非空子段的最大和。

输入 $n$ 和 $n$ 个整数，输出最大子段和。数据范围：$1\le n\le2\times10^5$，$|a[i]|\le10^4$。

例如，序列 2 -3 4 -1 2 1 -5 的最优子段为 4 -1 2 1，答案为 $6$。

思路

设 $dp[i]$ 表示以第 $i$ 个数结尾的最大子段和。

对于 $a[i]$，要么单独作为新子段，要么接在以 $a[i-1]$ 结尾的最优子段后面：

初始化 $dp[1]=a[1]$，从左到右计算。答案为 $\max_{1\le i\le n}dp[i]$。

注意：子段非空，答案不能初始化为 $0$；全为负数时，答案是最大的那个数。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200010;
int a[N];
int dp[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dp[1] = a[1];
    int ans = dp[1];
    for (int i = 2; i <= n; ++i) {
        dp[i] = max(a[i], dp[i - 1] + a[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$。