53. Maximum Subarray

problem description

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

algorithm analysis

最大连续子数组和，典型的动态规划问题。如果现在给出大小为3的数字，分别为1，2，3。他们的结果是6这时候，如果数组最后加入一个数字4，结果会变为10。这个例子说明，可以用之前的结果来简化求解现在结果的过程。这也是动态规划的思想。这里还有一种情况，就是如果当前和为负值的情况，这时候不能用前面的负值，应该使用当前值直接表示。

code

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

algorithm anlysis

一次循环使用以为数组保存最后结果，复杂度时间O(n)