• 【题意】给你一个整数数组 $a$ ，请你找出一个具有最大和的连续子数组
• 【状态表示】$dp[i]$ 表示以 $a[i]$ 结尾的最大子数组和
• 【状态转移】

$$\begin{equation} dp[i] = \left\{ \begin{array}{lr} a[i], & 不需要a[i]之前的数 \\ dp[i-1]+a[i], & 需要a[i]之前的数 \end{array} \right. \end{equation}$$

• 最后的结果就是 $max(dp[0], dp[2], \cdots, dp[n-1])$
• 状态的个数是 $O(n)$，转移是 $O(1)$，所以时间复杂度是 $O(n)$
• 由于 $dp(i)$ 只与 $dp(i-1)$ 有关，我们可以把 $dp$ 数组用一个变量 $now$ 代替

#include <bits/stdc++.h>
using namespace std;

int maxSum(vector<int>& a) {
    int n = a.size(), ans = a[0], dp = a[0];

	// dp(i): 以 a(i) 结尾的最大子数组和
    for (int i = 1; i < n; i++) {
        dp = max(a[i], dp + a[i]);
        ans = max(ans, dp);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << maxSum(a) << '\n';

    return 0;
}