题解 | #最大序列和#

#include <climits>
#include <iostream>
#include <cstring>

using namespace std;


const int N = 1000010;

long long dp[N];
long long A[N];
/* dp[i]表示以i结尾的最大子序列和
   dp[i]=A[i] or dp[i]=A[j]+A[j+1]+....+A[i-1]+A[i]
                      =dp[i-1]+A[i]

*/


int main() {

    int n;
    while (cin >> n) {
        dp[0]=0;
        for (int i = 1; i <= n; i++) {
            cin >> A[i];
        }
        for (int i = 1; i <= n; i++) {
            dp[i] = max(dp[i - 1] + A[i], A[i]);

        }
        long long ans = INT_MIN;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }

    return 0;
}