LeetCode 53 最大子序和

53.最大子序和

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

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

动态规划

此处寻找的是连续的子序列，要求子序列的和能够最大。重点依旧是动态规划数组的定义。

1. 动态规划数组的定义：定义动态规划数组 dp[n+1] ，其中 dp[i] 表示以 nums[i-1] 结尾的子序列的最大和。
2. 动态规划数组的推导：对于 dp[i] ，推导公式为 dp[i]=max(nums[i-1],nums[i-1]+dp[i-1])
3. 动态规划数组的初始化：对于 dp[0] 不存在序列，初始化为0即可
4. 动态规划数组的遍历顺序：从前向后遍历
5. 举例验证：对于 nums = [-2,1,-3,4,-1,2,1,-5,4] 对应的动态规划数组输出为 dp=-2,1,-2,4,3,5,6,1,5 ，结果为6，验证正确。

代码实现：由于只使用到了前一个状态，基于滚动数组实现

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

贪心实现

贪心的基本思想为：从当前数值 nums[i] 开始，不断进行元素的合并，将两个元素求和，合并为一个新得元素。再使用新的元素向后累加，若合并后的元素值小于0，那么对总体求和而言，这个首元素是负贡献的，将其舍弃，转而选取新的非负首元素，一定能够使得总的序列和更大。

代码实现：

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