参看网页

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;

    }

};