思路
求最大子序列和,我们可以使用动态规划的思路,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; }