Maximum Subarray

<-- algorithm

原题链接

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;
}