题解 | #连续子数组最大和#

动态规划

dp[i]是以第i个数为结尾的最大和

如果加了这个元素 还不如直接选这个元素 呢么就直接选择这个元素

#include <iostream>
using namespace std;

const int N = 2 * 100010;
long long a[N];
long long dp[N];

int main() {
    int n;
    cin >> n;
    long long res = -1e9;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++){
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}