053.md

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解析

动态规划经典题，只需遍历依次序列即可。用tmpres保存临时的和。若tmpres<0，那么就应该将tmpres重置为0， 因为负数加任何数都会变小。如果tmpres > 0，那么就比较一下tempres 和 result 的大小。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int tmpres = 0;
        for(int i = 0; i < nums.size(); ++i){
            tmpres = max(tmpres + nums[i], nums[i]);
            result = max(result, tmpres);
        }
        return result;
    }
};