LeetCode-53-最大子序和

LeetCode-53-最大子序和

题目描述

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

示例:
​
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路解析

这道题在LeetCode上的标签为简单，却花了我一下午的时间，看来我还是太菜了:(

一开始设计动态转移方程的时候我想岔了，我的思路是遍历数组，在每个点保存当前最大子序和；

这样一来，我就被各种情况掣肘，经常遇到考虑了情况A顾不上情况B的时候；

于是我偷偷的瞄了一眼题解，得到了一个官方的状态转移方程：

[dp[i]=max(dp[i-1],nums[i]) ]

乍一看感觉怎么会这么简单，不会是官方出错了吧，

仔细研究才发现真是厉害，自己还是太笨了，方程的思路在于：

每个点要组成子序列，只有两种选择，一是当前点作为起点，二是加入上一个点；

于是选择两种选择中最大的值保存起来，最后子序列的值为：

[ans=max(dp[i]) ]

总结

其实本题的只是常规的动态规划，之所以不得其解，是因为我的思路陷入了误区，以为状态转移方程一定要得到最后的解，其实完全可以求出阶段性的最优解，最后取最值即可。引以为戒。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int pre = 0, now = 0;
        for (int num:nums)
        {
            now = max(pre+num, num);
            sum = max(sum, now);
            pre = now;
        }
        return sum;
    }
};