leetcode 53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 额，我现在分不清这种方法是dp还是什么；

用temp记录连续子集的和， 如果连续子集比当前元素小，就把temp设置为当前值， max记录连续子集 的最大和。 感觉是dp

注意点：maxx的初始值应该为-2147483647，即整形的最小数

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