参看网页

http://www.tuicool.com/articles/UzmU7jb

1. 053

Maximum Subarray

2.算法

• DP：O(n)

http://www.cnblogs.com/grandyang/p/4377150.html

step:状态转移方程：sum[i]=max{sum[i-1]+a[i],a[i]}

max({sum(i)})

step:subarray的总体和大于0，认为其对后面有贡献，加入到之前的subarray

step:subarray的总体和小于0，认为其对后面无贡献，则另起一个subarray

3. 代码

// O(n) solution
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0], tmp = res;
        for (int i = 1; i < nums.size(); ++i) {
            tmp = max(tmp + nums[i], nums[i]);
            res = max(res, tmp);
        }
        return res;
    }
};