题解 | #最大子串和#

对于每个元素a[i]分两种情况

1. 以 $a[i]a[i]$ 为区间左端点构建一个新的连续区间

2. 将 $a[i]a[i]$ 并入 $a[i-1]a[i-1]$ 所属的连续区间

答案为每个连续区间的和取max

(下标从$11$开始到$nn$)

因此枚举每个 $a[i]a[i]$, 用状态转移方程 $dp[i]=max(a[i],dp[i-1]+a[i])dp[i]\; =\; max(a[i],\; dp[i\; -\; 1]\; +\; a[i])$ 得到 $11$到$ii$间所有连续区间和的最大值dp$[i][i]$ (即$dp[i]dp[i]$的意义)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long dp[N], a[N];

int main() {
    long long n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        dp[i] = max(a[i], dp[i - 1] + a[i]);//分两种情况,从i重新开始或和接上前一个
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}