算法题 最大子数组和

黑白客

前言

写这篇文章之前，我已经刷了一遍leetcod的top150道热题，一本剑指offer，牛客上一百多道题目的某企题库。
但是！ 我我最近重新去做题，发现我只是稍有头绪，完全和想象中的效果不一样。反思总结，我只是在为了刷题而刷题，因此今天准备拿这道刷法题开刀，深入去学习，分享这道题，这类题，以及做算法题常要想到的技巧和方法。
本题 leetcode 53 属于简单，经典型题目 此题还有很多变种，适合用来讲解动态规划的思路

1 问题

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

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

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

2 解题思路

认真阅读题目之后，我会有这样的疑惑。
题目要求是连续子数组，只是强调了连续。
那到底该从何开始，从何结束呢？
其实有点算法基础的我可以想到，应该将大问题化解成小问题。然后逐个击破！
一般思路，暴力解法-》找子问题逐个击破

第一种思路：

双层for循环，一个代表左指针，一个代表右指针，计算之间的结果
用一个int保存最大的结果，没计算完成一次，就比较一下大小，保存最大的结果。

这种思路没有问题，但是遇到打的数据就会超时了
下面是演示代码

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int next = 0;
        int len = nums.length;
        int i1 = 0;
        for (int i = 0; i < len; i++) {
            for (i1 = i; i1 < len; i1++) {
                next = 0;
                for (int i2 = i; i2 <= i1; i2++) {
                    next+=nums[i2];
                }
                res = Math.max(res,next);
            }
        }
return res;
    }

运行结果

//本地测试小数据
 System.out.println(solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
 //结果
 6
//提交之后
运行失败:
    Time Limit Exceeded

第二种思路：

仔细分析我们第一种思路中,其实用了这样一个方法，比如我们确定下来左指针之后，就去找了以左指针结尾的数中，最大的数。
你可能这么做了，但是你并没有发现上面这个逻辑
但是这很重要！！
大化小，小化无，这里我们就已经找到了子问题。
可不可以先解出子问题，然后再找它们之间的关系呢？
他们之间的关系，假如求出了所有以某个数结尾的结果，那么它们之间我们再选出最大的就可以。
解子问题
如果求最后一个数的结尾，那最大值就是它自己。
如果求倒数第二个数开始的最大值，就有两种情况
1 如果最后一个数求出的最大值是负数，那最大数就是它自己。
2 如果最后一个数求出的最大值是正数，那最大数就是它加上前一个数的最大数。
能想到这里基本已经解题了，
让我们思考，该如何想到这一步？在没有看答案，没有第三视角的情况下（毕竟真正做题的时候我们不知道这条路是对的）
首先想要解子问题，我们应该去分析一下每一个子问题，这没问题吧，我们思路总要往前一步试一试。
然后我们会发现最后一个子问题个结果就是它自己。 它很特别，也是最简单的。注意到这个数。
然后我们就去观察，为什么从最简单慢慢变复杂了，他们之间有什么关系
这很重要，这很重要，这很重要！！

找关系

找子问题之间的关系是很重要的一个思想。
看 只要我们沉下心来，慢慢分析，一步一步往下走，而不是脑子这条路想想，那条路想想也不知道结果 就处于一种混沌的状态了。
如果你脑子里有了其它的路线，你不妨也可以顺着往下走走，但是经验之谈，不是正确的路肯定充满坎坷，恐怕到最后你自己都验证不了，不过，还是要去走走，看看自己能走多远。 万一，在数学和地球一样呢，无论从哪里出发只要一直走总能到终点或者原点，到原点的话，就换个方向走呗。
当然了这要结合时间和效率，所以你还是来看我的文章，我帮你找正确的路哈哈，不过真正答题的时候，可千万不能放弃，思路不清晰也不要上来就写代码，可以先写伪代码，把逻辑搞清楚，那最后去写的时候就是简简单单啦。

逻辑搞清楚

ok 聊了这么多，就是激励一下每个被算法折磨的小伙伴，发现里面的奥秘，发现它的简单，然后我们继续吧。
分析倒数第二个复杂的原因是，它要判断它是最大的，还是说它加上后一个才是最大的。
头脑风暴开始， 那倒数第三个 最大的就是 判断自己本身是不是最大，是不是加上倒数第二个最大，是不是后面全加上最大。那倒数第四个，第五个，，， 完了这么多情况，我想不清楚啦。
（一般情况下，人的大脑超过2，就计算不清楚了，要确定的去看看倒数第二个情况有没有什么信息要提取）
（一般情况下，它们之间的关系都和子问题计算出来的结果有关系）
啊 你听到我括号里的话是不是有一种身处迷宫，忽然传出一个声音，告诉了你前进的道路，（哈哈，我自行脑补的）。
好吧记住我上面说的两句话，那就是这篇文章的精华了，你的指路明灯。以后可以慢慢验证。
那我们看一下，我们计算倒数第二个的最大值，就需要判断倒数第一个的最大值， 倒数第一个最大值，就代表了之后所有情况的最大值是多少，那我们再新加一个倒数第二，的情况呗。在之前最大值的情况下，加一个倒数第二求最大值。
如果之前最大值是一个负数，那不用说了，之前所有情况的最大值还是一个负数，那到了倒数第二个值的时候最大值就是自己，因为 加一个负数等于减嘛
如果是正数就加上前面的最大值 。就是这个数的最大值。

代码怎么写呢？

1.子问题的定义
2.解决子问题
3.确定子问题之间的关系
4.通过关系解决问题

啰啰嗦嗦这么多，估计思路大家都知道了，还有困惑就留言评论帮你解答吧

1. 子问题 定义 : 以某个数结尾的最大值是多少
2. 解决子问题： 创建一个和传入进来的数组一样大的数组，记录相同下标下的数 以这个数结尾的最大子序列最大值是多少
3. 确定子问题之间的关系， 这一步就等于在解决第二步。关系就是如果前一个最大值是正数就相加求最大值，负数的话本身就是最大值。
   4.通过关系解决问题 再求出最大值之间的最大值，就是整个数组子数组的最大值

演示代码

    class Solution {
        public int maxSubArray(int[] nums) {
            int res = nums[0];
            int len = nums.length;
            int[] resArray = new int[len];
            resArray[len - 1] = nums[len - 1];
            for (int i = len - 2; i >= 0; i--) {
                resArray[i] = Math.max(resArray[i+1]+nums[i],nums[i]);
            }
            for (int i = 0; i < len; i++) {
                res = Math.max(res,resArray[i]);
            }
            return res;
        }
    }

运行结果

解答成功:
    执行耗时:2 ms,击败了44.03% 的Java用户
    内存消耗:50.9 MB,击败了29.82% 的Java用户

ok 到这里已经顺利解决这个问题， 但是还有一些需要优化的地方，那就是空间优化

3  空间优化

这个就算是选修了哈哈，因为一般没有太高的要求，只要你不是上来new int[Integer.MAX_VALUE]

其实上面为了让大家看的清楚，我把判断最大值重新写了一个for，其实在第一个for里面我们就可以判断，那我们也就不需要再保存一个数组，只保留上一个数的最大子序列值和这个比较就可以

演示代码

    class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            int res = nums[len-1];
            int next = nums[len-1];
            for (int i = len - 2; i >= 0; i--) {
                next = Math.max(next+nums[i],nums[i]);
                res = Math.max(res,next);
            }

            return res;
        }
    }

运行结果

解答成功:
    执行耗时:1 ms,击败了100.00% 的Java用户
    内存消耗:50.4 MB,击败了82.17% 的Java用户

4 总结补充

这道题可以简单归纳总结出求解动态规划类问题的解题思路

1. 确定，理解题意
2. 定义子问题，加修饰词，比如题目求数组的子序列最大和，我们求以某某数结尾的最大子序列之和
3. 找子问题之间的关系，状态转移，到解出我们要接触的问题，等于头和尾有了，怎么根据尾找到头
4. 优化，特殊值判断，特殊值容易再前面混淆你的思路，做题时有些可以忽略，不要想的太复杂，最后统一对特殊值做判断也可以

最后补充一下 后无效性，我们没有涉及到，但是再翻阅资料的时候发现这个思想也挺重要的，
就是定义子问题时，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。

李煜东著《算法竞赛进阶指南》，摘录如下：

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」