53. 最大子数组和

• 思路
  贪心：
  局部最优：如果累加和遇到负数，则将累加和置0，并重新计算累加和
  全局最优：获得最大数组和

class Solution 
{
public:
    int maxSubArray(vector& nums) 
    {
        int res = INT_MIN;
        int tempSum = 0;
        
        if(nums.empty())
        {
            return res;
        }
        
        for(int i = 0; i < nums.size(); ++i)
        {
            tempSum += nums[i];
            
            res = max(res, tempSum);
            
            if(tempSum <= 0)//如果累加和遇到负数，则将累加和置0，并重新计算累加和
            {
                tempSum = 0;
            }
        }
        
        return res;
    }
};

DP：

class Solution 
{
public:
    int maxSubArray(vector& nums) 
    {
        if(nums.size()==1)
        {
            return nums[0];
        }

        vector dp(nums.size(),0);//dp[i]：包括下标i之前的最大连续子序列和为dp[i]
        dp[0]=nums[0];
        int res=dp[0];
        for(int i=1;ires)//保存最大值
            {
            res=dp[i];
            }
        }                                        
        return res;
        }
};