算法题 最大子数组和
# 前言写这篇文章之前，我已经刷了一遍leetcod的top150道热题，一本剑指offer，牛客上一百多道题目的某企题库。
但是！ 我我最近重新去做题，发现我只是稍有头绪，完全和想象中的效果不一样。反思总结，我只是在为了刷题而刷题，因此今天准备拿这道刷法题开刀，深入去学习，分享这道题，这类题，以及做算法题常要想到的技巧和方法。
`本题 leetcode 53 属于简单，经典型题目` 此题还有很多变种，适合用来讲解动态规划的思路
# 1 问题
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 的和最大，为 6 。
示例 2：
输入：nums =
输出：1
示例 3：
输入：nums =
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
# 2 解题思路
> 认真阅读题目之后，我会有这样的疑惑。
> 题目要求是连续子数组，只是强调了`连续`。
> 那到底该从何开始，从何结束呢？
> 其实有点算法基础的我可以想到，应该将大问题化解成小问题。然后逐个击破！
> 一般思路，暴力解法-》找子问题逐个击破
## 第一种思路：
> 双层for循环，一个代表左指针，一个代表右指针，计算之间的结果
> 用一个int保存最大的结果，没计算完成一次，就比较一下大小，保存最大的结果。
> 这种思路没有问题，但是遇到打的数据就会超时了
> 下面是演示代码
```java
public int maxSubArray(int[] nums) {
int res = nums;
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;
}
res = Math.max(res,next);
}
}
return res;
}
```
> 运行结果
```java
//本地测试小数据
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.通过关系解决问题 再求出最大值之间的最大值，就是整个数组子数组的最大值
演示代码
```java
class Solution {
public int maxSubArray(int[] nums) {
int res = nums;
int len = nums.length;
int[] resArray = new int;
resArray = nums;
for (int i = len - 2; i >= 0; i--) {
resArray = Math.max(resArray+nums,nums);
}
for (int i = 0; i < len; i++) {
res = Math.max(res,resArray);
}
return res;
}
}
```
> 运行结果
```java
解答成功:
执行耗时:2 ms,击败了44.03% 的Java用户
内存消耗:50.9 MB,击败了29.82% 的Java用户
```
> ok 到这里已经顺利解决这个问题， 但是还有一些需要优化的地方，那就是空间优化
# 3空间优化
> 这个就算是选修了哈哈，因为一般没有太高的要求，只要你不是上来new int
> 其实上面为了让大家看的清楚，我把判断最大值重新写了一个for，其实在第一个for里面我们就可以判断，那我们也就不需要再保存一个数组，只保留上一个数的最大子序列值和这个比较就可以
演示代码
```java
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int res = nums;
int next = nums;
for (int i = len - 2; i >= 0; i--) {
next = Math.max(next+nums,nums);
res = Math.max(res,next);
}
return res;
}
}
```
> 运行结果
```java
解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:50.4 MB,击败了82.17% 的Java用户
```
# 4 总结补充
这道题可以简单归纳总结出求解动态规划类问题的解题思路
1. 确定，理解题意
2. 定义子问题，加修饰词，比如题目求数组的子序列最大和，我们求以某某数结尾的最大子序列之和
3. 找子问题之间的关系，状态转移，到解出我们要接触的问题，等于头和尾有了，怎么根据尾找到头
4. 优化，特殊值判断，特殊值容易再前面混淆你的思路，做题时有些可以忽略，不要想的太复杂，最后统一对特殊值做判断也可以
最后补充一下 `后无效性`，我们没有涉及到，但是再翻阅资料的时候发现这个思想也挺重要的，
就是定义子问题时，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。
李煜东著《算法竞赛进阶指南》，摘录如下：
>为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」
页:
[1]