2017/03/25
题目描述
寻找数列的最大子列和。
分析
动态规划问题,见leetcode-3的讲解。
定义s[i]是以第i个元素结尾的最大子列和。
nums[i] + s[i-1] ,if s[i-1] >= 0
s[i] ={
nums[i] ,if s[i-1] < 0
代码
int maxSubArray(vector<int>& nums) {
int curSum = nums[0];
int maxSum = curSum;
for (int i = 1; i < nums.size(); i++) {
curSum = nums[i] + (curSum > 0 ? curSum : 0);
if (curSum > maxSum) maxSum = curSum;
}
return maxSum;
}