题解 | #连续最大和# 动态规划

经典动态规划

定义dp[i]为遍历到第i位时的连续最大和

前缀和<0时，说明前面的负数太多了，使当前的总和小于0，应当抛弃掉前面的数，直接从当前遍历到的数“另起炉灶”

详细版：

for (int i = 1; i < N; i++) {

if(dp[i-1]<0){

dp[i]=nums[i];

}else{

dp[i]=dp[i-1]+nums[i];

}

}

合并起来就是：

dp[i] = max(nums[i], dp[i - 1] + nums[i]);

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

int main() {
    int N;
    while (cin >> N) {
        int num;
        vector<int> nums;
        for (int i = 0; i < N; i++) {
            cin >> num;
            nums.push_back(num);
        }
        vector<int> dp(N, 0);
        dp[0] = nums[0];
        for (int i = 1; i < N; i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
    return 0;
}

时间复杂度：主要是遍历数组的开销，O(N)

空间复杂度：主要是dp数组的开销，O(N)