最大序列和

思路

求最大子序列和，我们可以使用动态规划的思路，dp[i] 表示以 nums[i] 结尾的最大和，那么 dp[i] = max(dp[i-1] + nums[i], nums[i]) = dp[i-1] > 0 ? dp[i-1] + nums[i] : nums[i]

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<int> dp(n, 0);
        int num, ans = INT_MIN;
        for(int i = 0; i < n; i ++){
            cin >> num;
            if(i == 0) dp[i] = num;
            else dp[i] = dp[i-1] > 0 ? dp[i-1] + num : num;
            ans = max(dp[i], ans);
        }
        cout << ans << endl;
    }
    return 0;
}

当然，我们应该尽可能地优化空间复杂度，因为我们每次循环只使用到了 dp[i-1] 来更新 dp[i]，我们完全可以使用 O(1) 的空间复杂度。

#include<iostream>
#include<climits>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        int dp = 0;
        int num, ans = INT_MIN;
        for(int i = 0; i < n; i ++){
            cin >> num;
            if(i == 0) dp = num;
            else dp = dp > 0 ? dp + num : num;
            ans = max(dp, ans);
        }
        cout << ans << endl;
    }
    return 0;
}