53.最大子数组和

发表于： 分类于：
字数： 884 阅读：≈ 2分钟

😄53.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

思路

贪心基本思想

当前元素加上之后只要和不为负数，就可以对后面的元素产生正面的影响，至少相加之后不会拖后面元素后腿，所以只要是正数就一直加

相加的过程中，可能会出现正数被后面的负数拉低的情况，此时就需要一个全局的res来统计出现的最大和，当出现负数和时，对后面的元素无法起到正面的影响，会拖后腿，还不如不加，所以当前的和直接变为0，从当前位置开始重新累加

为正就继续加，为负就直接为0

执行流程

  1. 从前向后遍历
  2. 正数和就直接向后加，负数和就变成0
  3. 统计遍历过程中的最大值作为最终的结果

动态规划思想

当前位置的和肯定与之前的元素和有关，所以使用动态规划解题

当前元素加上之前的和还不如当前元素本身大，说明前面的和为负数，此时还不如不加，对应贪心中的步骤就是和置0，然后从当前位置开始加，对应到动态规划中，就是当前位置的和变成自身，以供后面的元素使用

后面的元素加上前面的和变得更大，那么就继续加，更新当前的dp数组，对应的递推方程为： $$ dp[i+1]=max(dp[i]+nums[i],nums[i]) $$

dp[i]的含义是累加到第i个元素得到的最大和

更新dp的过程中需要记录最大的和作为最终的结果

对当前元素有增益就加，没增益就不加

执行流程

  1. 初始化dp数组全为0，对累加的和没有影响
  2. 按照递推方程更新dp数组
  3. 更新过程中统计最大的和作为最终的结果

代码

贪心 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //记录最大值的标志
        int res=INT32_MIN;
        //记录序列的累加和
        int sum=0;
        //遍历容器
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            //每走一步就统计一下最大值
            //并且必须放在累加之后，因为有可能最大序列和是负数
            //此时就会
            if(sum>res)
                res=sum;
            //小于零的序列和舍弃
            if(sum<0)
                sum=0;
        }
        return res;
    }
};

动态规划 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

总结

不管是贪心还是动态规划，只要对当前元素有正面的影响，前面的元素就应该累加到当前元素上，如果没有正面的影响，前面的累加和结果就应该丢弃，对应到贪心中就是累加和为0，对应到动态规划中就是当前的dp变成当前元素本身，也相当于累加和为0