leetcode-53 最大子序和 原 荐

题目

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

示例:

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

分析

第一感觉要用到动态规划，就需要找出状态和状态转移方程。找状态至关重要，状态找的好，对应的状态转移方程可能就非常简单，状态找的不好，对应的状态转移方程可能就比较麻烦。

找状态一般找问题本身或者问题的等价问题，先尝试以问题本身作为状态来分析，如果对应的状态转移方程很复杂，再根据问题尝试有没有其他的等价问题来作为状态

初步分析

首先以题目作为状态

f(n)为前n个元素的最大子序和的值

由于f(n)只是前n个元素中的最大子序和，这个子序可能并不包含nums[n]元素，所以再来一个nums[n+1]时，并不太好确定f(n+1)，需要分如下2种情况来分析：

• 当最大子序包含nums[n]，则f(n+1)的求解如下：

  如果nums[n+1]>0 则f(n+1)=f(n)+nums[n+1]
  如果nums[n+1]<0 则f(n+1)=f(n)

• 当最大子序不包含nums[n]，则f(n+1)的求解如下：

  来一个nums[n+1]只会对以nums[n]结尾的每个子序的最大和产生更新影响，同时如果前面的子序和都是负的话，则nums[n+1]则是最大子序和，所以只需要计算出这部分更新后的最大子序和与f(n)对比求最大值即为f(n+1)的最大子序和
  
  即f(n+1)=max(f(n),以第n个元素结尾的最大子序和+nums[n+1],nums[n+1])

这里我们就会发现针对上述f(n)的状态转移方程还是非常复杂，并且状态转移方程里面还包含了一个暂时没有结论的问题即：以第n个元素结尾的最大子序。这个问题其实也是一个动态规划，这个问题的解如下：

g(n)为以第n个元素结尾的最大子序和，则g(n+1)的解如下：

当g(n)>0 则g(n+1)=g(n)+nums[n]
当g(n)<=0 则g(n+1)=nums[n]

所以这个g(n)问题还是很好求解的。

综上所述对于f(n)的求解是动态规划里面还嵌套动态规划，简述为父动态规划嵌套了子动态规划，不过还好，每一轮都可以求出这一轮的子动态规划值，然后利用这个值进而可以求出父动态规划的值。所以对于上述思路还是可以做出来结果的。

不过上述思路也太复杂了，很可能是我们选择的状态不合适导致的，所以此时我们就需要转换思路有没有更合适的状态

转换思路

等价命题的转换并没有太多的规律可循，与实际题目息息相关，可能需要从上面的初始分析中进行提取。

比如上面的g(n)还是很简单的，能否充分利用g(n)来解题？

假如我知道了每个g(n)的值，那么f(n)其实就是max(g(k)) 0<=k<=n

所以整个问题其实就清晰明了了很多，最终是以第N个元素结尾的最大子序和作为状态来进行动态规划，利用动态规划的结果来求解最终的问题

套路总结

• 很多时候动态规划的出题者不会给你一个一眼就能看出的状态，这时候就可能需要重新去找一个等价命题的状态，比如对于该题，你能够快速想到g(n)这个状态
• 假如想不到对应的等价命题的状态，看能否根据已有的简单的动态规划的解来求解问题，比如我已知了g(n)，能够利用g(n)作为突破口来推导目标问题的答案
• 某个子序的解可能是所有以某个元素结尾的子序的解的max或者min等其他函数，以某个元素结尾的子序的解可以简化好多问题

代码

利用一个变量来记录g(n-1)的值，通过g(n-1)和状态转移方程来求解出g(n)，同时用一个变量来记录g(n)的最大值即为f(n)

public static int maxSubArray(int[] nums) {
    int fn = nums[0];
    int lastGn = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (lastGn > 0) {
            lastGn += nums[i];
        } else {
            lastGn = nums[i];
        }
        if (lastGn > fn) {
            fn = lastGn;
        }
    }
    return fn;
}

代码很简单，关键点不在于解决了此题，而是在于解决此题的思考过程，其中还是有一些套路可循的

跑分

欢迎关注微信公众号：乒乓狂魔