[数据结构与算法]【LeetCode】动态规划专题

前言

这里面记录的是自己刷力扣题目的过程，这一部分记录的则是动态规划相关的题目，分享的同时方便后续自己回顾，如果发现有什么问题欢迎提出。

后续可能会去研究一下贪心了，毕竟在写的时候有过需要贪心配合解决的题型。

1、509. 斐波那契数

1.1、题目描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

• F(0) = 0，F(1) = 1
• F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

1.2、示例

1.3、提示

• 0 <= n <= 30

1.4、个人思考

这个是老熟人了斐波那契数，因为在刚开始接触编程的时候，这道题目便是一道典型的练习题，学习数组或者递归的时候想必练习题后面肯定有一道这个题目。

先说一下自己的看法吧，毕竟是一个动态规划的专题，就得从动态规划的角度出发，而对于暴力递归和暴力遍历的解法就不赘述了。

首先肯定是动态规划的三大关键，分别是定义dp数组、找出初始化值和找出关系方程式。而针对这道题目，这三个关键我是这么定义的：

• dp数组：这里明显使用的是一维数组充当dp数组，这是为什么呢？从题目我们可以看出来整个斐波那契数列是一维的，而非二维的，并不需要创建一个二维的数组来实现这一问题。同时需要注意的是，dp数组的大小我们需要设置成 n+1，并不能是 n，这是因为我们需要得到的是 F(n)，同时还需要 F(0) 的值，因此，我们需要多一个空间来存放 F(0)；
• 初始值：根据斐波那契数的特性，后面的每一项数字都是前面两项数字的和，因此初始化值需要求出 F(0) 和 F(1)，即 dp[0] 和 dp[1]。至于 dp[2]需不需要初始化，这个需要根据情况而定，简单粗暴的方法就是把 dp[2] 的值求出进行对比验证一下，不过在这道题目中不需要用到该值；
• 关系方程式：在这道题目中当我们清楚了初始值是哪些之后，就很轻易的知道了这个关系方程式。同样根据斐波那契数的特性，后面的每一项数字都是前面两项数字的和，可以得出 dp[i] = dp[i-1] + dp[i-2]。

1.5、代码实现

class Solution {
    public int fib(int n) {
        // 边界值考虑
		if (n == 0 || n == 1) {
			return n;
		}
		// 定义dp数组，数组元素含义为下标所在数便为第几个斐波那契数
		int[] dp = new int[n + 1];
		// 定义初始值
		dp[0] = 0;
		dp[1] = 1;
		// 遍历n次求最终值
		for (int i = 2; i <= n; i++) {
			// 定义关系方程式，根据斐波那契数性质得出
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[n];
    }
}

2、746. 使用最小花费爬楼梯

2.1、题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

2.2、示例

2.3、提示

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

2.4、个人思考

这明显也是一道动态规划的题目，不知道大家有没有做过另外一道上楼梯的题目，也是类似的，题目意思大概就是可以从前一阶或前两阶跳到当前阶梯，求上到楼梯顶部有多少种办法？而这道题目就相当于是一个升级版，在简单的爬楼梯题目中，我们可以很简单的发现当前楼梯只可能从前一阶或前两阶上到，那么关系方程式就能显而易见了，即 dp[i] = dp[i-1]+dp[i-2]。那么是不是这个方程式在这里也适用呢？

并不是的。因为这里需要求得上到顶部的最小花费，并不是简单的相加。因此我们一样需要找到动态规划中的三大关键元素：

• dp数组：这里同样是简单的一维情况，注意的是数组的长度需要设置成 cost数组的长度+1，因为需要存放多一个零号单元，这应该算是动态规划的惯例或者说是套路吧，因为一般情况下最后返回的为 dp[length]（根据个人目前刷题情况来看）。那么数组中存放元素的含义为：下标对应楼梯的第几阶，下标对应元素为走到该阶梯的最小花费；
• 初始值：这里的初始值和简单的爬楼梯不同，只需要找到0号阶梯与1号阶梯的对应的dp数组初始值即可，因为我们第一次上楼梯只能从这两个阶梯上去，因此这两个的初始值都为零。而根据后面推导出来的关系方程式计算可知，2号阶梯并不需要单独计算；
• 关系方程式：这里就需要进行观察才能推导出来了。以第三阶梯为例，第三阶梯为是有可能从第一阶梯和第二阶梯跳上来的，只是需要在第一阶梯与第二阶梯中挑选最小花费即可，而这个最小花费则是 跳上第一阶梯的花费+第一阶梯向上爬的花费 和 跳上第二阶梯的花费+第二阶梯向上爬的花费 中取最小值，因为我们不可能只看那个阶梯向上爬的花费，还得看跳上那个阶梯的花费是多少，进行综合比较，一个 100+1 和 1+50 的，我们肯定会选择后者而不会选择前者。因此我们就可以推导出关系方程式为 dp[i] = Min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

在介绍完成之后是不是还有点蒙，我们以示例2的输入为例进行一个进一步解释，这里对dp数组进行初始化：

按照公式，dp数组从下标2-10对比的情况如下：

• 下标2：Min(0+1, 0+100) = 1;
• 下标3：Min(0+100, 1+1) = 2;
• 下标4：Min(1+1, 2+1) = 2;
• 下标5：Min(2+1, 2+1) = 3;
• 下标6：Min(2+1, 3+100) = 3;
• 下标7：Min(3+100, 3+1) = 4;
• 下标8：Min(3+1, 4+1) = 4;
• 下标9：Min(4+1, 4+100) = 5;
• 下标10：Min(4+100, 5+1) = 6。

这个时候dp数组就已经全部填充完毕，最后一个元素值便是我们最终想要的答案。

2.5、代码实现

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        // 定义dp数组，因为Java数组存在初始化值且为零，因此不需要显示初始化
		int[] dp = new int[length+ 1];
        // 遍历从2开始，因为0、1为初始化值
		for (int i = 2; i <= length; i++) {
            // 关系方程式求值
			dp[i] = Math.min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2]);
		}
        // 返回计算结果
		return dp[length];
    }
}

2.6、滚动数组优化

这写完这道题目的时候去参考了题解，发现了滚动数组这一思想。简单来说，滚动数组就能够帮助我们降低空间复杂度，用更少的空间来解决动态规划。从上面常规的解法中可以看出来，对于dp数组而言，我们需要的只是 dp[length]、dp[length-1]、dp[length-2] 这三个值，其余的只是参与其中一次运算便不再使用了，因此滚动数组的思想便是利用固定长度的数组元素充当所必须的三个值，在循环中通过覆盖实现动态刷新滚动数组中的值，从而达到节约空间的效果。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 定义滚动数组
		int[] dpRolling = new int[3];
		for (int i = 2; i <= cost.length; i++) {
			// 常规dp利用关系方程式进行计算
			// dp[i] = Math.min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2]);
			
			// 利用滚动数组
			dpRolling[2] = Math.min(cost[i-1] + dpRolling[1], cost[i-2] + dpRolling[0]);
			dpRolling[0] = dpRolling[1];
			dpRolling[1] = dpRolling[2];
		}
		return dpRolling[2];
    }
}

实际上在我的LeetCode执行结果上看来并没有什么区别，甚至还比常规的解法内存消耗更高，这猜测是测试用例的问题，当cost数组特别短时滚动数组的优势并不明显，当长度达到一定程度时，我们将会节省 cost.length - dpRolling.length 的空间。

3、198. 打家劫舍

3.1、题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

3.2、示例

3.3、提示

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

3.4、个人思考

在按照自己的想法写完并能够正确跑之后，才发现原来自己的思路和官方的题解不太一样，这里主要介绍我个人的一些想法，然后在后面再贴上我对官方题解的理解。

首先这道题目和简单的动态规划不同，不同在有特殊的条件限制，即如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，且不触动警报装置的情况下顺到东西才行。一开始我在思考这道题目的时候就拿着和常规动态规划一样的思想：既然求的是能偷窃到的最高金额，那么我是不是就可得出我走到的这一间房子能获取到的最高金额等于当前房子的金额+前面房子能拿到的最高金额呢？那么这样子的话核心三件套就可以这么定义：

• dp数组：在这道题目中其实我并没有设计dp数组，而是使用了原有的nums数组充当dp数组的角色，其中每个元素的值即为走到该房间时能拿到的最高金额，只需要在nums数组原有的值上添加前面房子能拿到的最高金额即可；
• 初始值：对于这个思路，第一和第二个房子是需要初始值的，且初始值就是其本身的元素。同时第三个房子也是需要进行初始值计算的，且初始值为第一个房子和第三个房子的值相加，具体原因与下面的关系方程式有关；
• 关系方程式：先把方程式贴出来“nums[i] += Math.max(nums[i-2], nums[i-3])”，最终的结果值取Math.max(nums[nums.length - 1], nums[nums.length - 2])。
  • 先解释为什么结果取后面两个去最大值吧：回想这道题目的特殊性，是不能够偷取隔壁房子的，因此最终要么是偷到最后一个房子的时候是最大金额，要么就是倒数第二个是最大金额，转为代码翻译便为Math.max(nums[nums.length - 1], nums[nums.length - 2])；
  • 接下来是方程式的推导，其实在这道题目中我有点硬推的意思在里面。在贴出来的公式中可以看到，当前的最大值是加上了当前下标前二和前三的最大值，因为不能偷隔壁的，那么前面的最大值肯定在前。那么为什么只需要加上前二和前三的最大值而不需要将更前面的也考虑进来呢？通过画图其实可以看出来的，前四前五乃至更前的已经由前二和前三考虑到了，因此只需要在前面建立下的基础往后累加就行，因此得到方程式nums[i] += Math.max(nums[i-2], nums[i-3])。

3.5、代码实现

class Solution {
    public int rob(int[] nums) {
        // 长度判断，为1直接返回
		if (nums.length == 1) {
			return nums[0];
		}
		// 长度判断，为2返回前两个最大的值
		if (nums.length == 2) {
			return Math.max(nums[0], nums[1]);
		}
		// 大于等于3时，需要计算第三个的初始值，因为关系方程式中需要减3
		nums[2] += nums[0];
		// 循环遍历计算，使用原地计算
		for (int i = 3; i < nums.length; i++) {
			nums[i] += Math.max(nums[i-2], nums[i-3]);
		}
		// 比较数组最后两个元素，取较大值为返回值
		return Math.max(nums[nums.length - 1], nums[nums.length - 2]);
    }
}

3.6、力扣题解

class Solution {
    public int rob(int[] nums) {
        // 特殊情况
        if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 创建dp数组
        int[] dp = new int[nums.length];
        // 初始值
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = Math.max(nums[0], nums[1]);
        for (int i = 3; i < nums.length; i++) {
            /*
                设： 有 nn 个房子，前 nn 间能偷窃到的最高金额是 dp[n]dp[n] ，前 n-1n?1 间能偷窃到的最高金额是 dp[n-1]dp[n?1] ，此时向这些房子后加一间房，此房间价值为 num ；
                加一间房间后： 由于不能抢相邻的房子，意味着抢第 n+1n+1 间就不能抢第 nn 间；那么前 n+1n+1 间房能偷取到的最高金额 dp[n+1]dp[n+1] 一定是以下两种情况的 较大值 ：
                不抢第 n+1n+1 个房间，因此等于前 nn 个房子的最高金额，即 dp[n+1] = dp[n]dp[n+1]=dp[n] ；
                抢第 n+1n+1 个房间，此时不能抢第 nn 个房间；因此等于前 n-1n?1 个房子的最高金额加上当前房间价值，即  dp[n+1] = dp[n-1] + num
             */
            // 定义转换公式：dp[n+1]=max(dp[n],dp[n?1]+num)，即在下面两种情况中选择最大值
            // 不偷这一家，值还是上一家的最大值
            // 偷这一家，值为隔一家的最大值加上这一家的值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
    }
}

4、740. 删除并获得点数

4.1、题目描述

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

4.2、示例

4.3、提示

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

4.4、个人思考

做这道题目的时候其实自己并没有太多的思路，甚至想着这道题是不是强用DP来解题的，在观看了题解思路之后，才发现是我格局小了。看了许多的题解，都在说这道题目的思路和上面的 打家劫舍 思路很相似，甚至你会了上面那道题目，这道题目就是信手拈来(我可能没有手)。

在观看了官方题解以及其它优秀前辈的题解之后，好像懂了又好像没懂，懂得是他们说的思路，不懂的是好像看完还不知道怎么实现。

因此在了解了一个大概思路之后，自己打开了IDEA开始上机，尝试着按照思路翻译一下代码，先列一下大部分题解的思路吧，主要有三个，两个看懂了，一个没看懂：

• 看懂其一：将数组排序之后，使用哈希表对点数的出现次数进行记录，之后开始遍历排序好的数组，通过点数与哈希表中的出现次数进行相乘得到当前点数能获取的数值，再通过关系方程式得到最大点数即可。参考题解：这小偷又来偷了！他怎么这么聪明！；
• 看懂其二：遍历给定的 nums数组 获取到数组中的最大值 max，从而定义一个大小为 max + 1 的新数组 times，新数组中下标对应 nums数组 中的点数，而新数组中的元素则是记录着点数的出现次数。那么之后同样通过遍历与关系方程式得到最大点数。参考题解：【宫水三叶】转换为序列 DP 问题进行求解；
• 看不懂的官方：删除并获得点数[官方]

因为实现过程是由自己完成的，那么我就分别对应对应上面的两个看懂的思路，讲讲我自己是如何找到初始值与关系方程式并且实现的，同时本着勤俭持家的优良传统，两种实现方式都是通过滚动数组来代替传统的DP数组。

4.5、代码实现一

将数组排序之后，使用哈希表对点数的出现次数进行记录，之后开始遍历排序好的数组，通过点数与哈希表中的出现次数进行相乘得到当前点数能获取的数值，再通过关系方程式得到最大点数即可。

这个是上面讲到的思路，这种刚开始我核心在想的是：我排序之后怎么避免遍历到重复的点数。因为每次遍历都已经是将点数与出现次数相乘了，再遍历重复点数的话难免会得到脏数据。因此后续想到了一个很简单粗暴的方法，常规的 for 循环中结束一次循环不是 i++ 嘛，那么我就可以从这里下手，又刚好已经得到了记录点数出现次数的哈希表，因此就可以将其改成 i += map.get(nums[i])，意为每次会跳过当前点数出现的次数步，从而避免遍历到重复点数。

以上便是实现途中的细节。*路人甲：废话了这么多，那我初始值这些怎么找呢！！！*稍安勿躁，这就分别介绍DP中的三大关键要素：

• DP数组：这里其实前面提及到了，这里使用的是滚动数组，分别对应走到三个相邻点数时所能得到的点数最大值；
• 初始值：在写了几个DP题之后会发现，只要是滚动数组，里面的值一般都是要都赋值的。这里三个值分别为 0, nums[0]*map.get(nums[0]), rollArray[1]，其中的零是用于占位，避免后面的下标减二时出现越界异常，后面两个数值为第一个点数能获取到的值；
• 关系方程式：这里根据题目一共有两种情况。
  • 如果相邻的两个点数数值差为1时，小偷就会看当前位置的点数加上前前个位置的点数大，还是上一次的位置的点数大。方程式为：rollArray[2] = Math.max(nums[i] * time + rollArray[0], rollArray[1]);
  • 如果相邻的两个点数数值差不为1时，这个好啊，小偷直接将当前位置的点数连带上一次位置的点数一起带走。方程式为：rollArray[2] = nums[i] * time + rollArray[1];

public int deleteAndEarn(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    // 数组顺序排序
    Arrays.sort(nums);
    // 定义Map集合存放点数对应的出现次数
    Map<Integer, Integer> map = new HashMap<>();
    // 遍历收集点数的出现次数
    for (int num : nums) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    // 使用滚动数组
    int[] rollArray = new int[3];
    // 赋初始值
    rollArray[1] = nums[0] * map.get(nums[0]);
    rollArray[2] = rollArray[1];
    // 遍历获取最大值
    for (int i = map.get(nums[0]); i < nums.length; i += map.get(nums[i])) {
        Integer time = map.get(nums[i]);
        // 如果这个点数与上一个点数的数值差为1
        if (nums[i] - nums[i-1] == 1) {
            // 取max(当前位置能获取的点数+位置i-2能获取的点数, 位置i-1能获取的点数)
            rollArray[2] = Math.max(nums[i] * time + rollArray[0], rollArray[1]);
        } else {
            // 数值差不等于1时，直接取上一个点数能获取的最大值 + 当前点数能获取的最大值
            rollArray[2] = nums[i] * time + rollArray[1];
        }
        // 更新滚动数组
        rollArray[0] = rollArray[1];
        rollArray[1] = rollArray[2];
    }
    return rollArray[2];
}

这种思路其实我自己的实现方式并不好，因为性能太拉跨……

4.6、代码实现二

遍历给定的 nums数组 获取到数组中的最大值 max，从而定义一个大小为 max + 1 的新数组 times，新数组中下标对应 nums数组 中的点数，而新数组中的元素则是记录着点数的出现次数。那么之后同样通过遍历与关系方程式得到最大点数。

这是上面提及到的思路，这个思路其实是我刚开始就看到的，和我刚接触到这道题目的时候一个粗糙思路有点相似，但是自己想着定义这么大的数组，万一刚好只给了一个数，刚好是最大值，那岂不是会浪费掉数组中的绝大部分空间。没想到实现之后，反而是更优解来的，说到的这种情况是这一思路的最差情况。

这里没有太多的细节，基本上就是下标对应点数，元素对应次数，只是三大关键要素和思路一有所偏差：

• DP数组：这里没有偏差，同样是滚动数组；
• 初始值：这里偏差不大，滚动数组第一个还是零，第二和第三为新数组 times 的第一个元素，即下标为1对应的次数，严谨一点的话是点数，因为当点数为1时，那么总点数就等于出现的次数；
• 关系方程式：这里就会少了一种情况，因为在新数组 times 的遍历过程中，每一次都是 i++，从而导致每个相邻点数的数值差都是1，因此关系方程式为：rollArray[2] = Math.max(rollArray[1], times[i] * i + rollArray[0]);。

public int deleteAndEarn(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    } else if (nums.length == 1) {
        return nums[0];
    }
    // 遍历数组拿到最大值
    int max = 0;
    for (int num : nums) {
        max = Math.max(max, num);
    }
    // 以数组最大值+1为新数组长度，下标对应点数，元素对应点数出现的次数
    int[] times = new int[max + 1];
    // 遍历nums数组获取点数出现次数
    for (int num : nums) {
        ++times[num];
    }
    // 定义滚动数组
    int[] rollArray = new int[3];
    // 赋初始值
    rollArray[2] = times[1];
    rollArray[1] = rollArray[2];
    // 循环获取最大点数
    for (int i = 2; i < times.length; i++) {
        // 因为每次点数即下标数值差都为1，因此都取max(当前位置能获取的点数+位置i-2能获取的点数, 位置i-1能获取的点数)
        rollArray[2] = Math.max(rollArray[1], times[i] * i + rollArray[0]);
        // 更新滚动数组
        rollArray[0] = rollArray[1];
        rollArray[1] = rollArray[2];
    }
    return rollArray[2];
}

除了这里框出来的两个提交记录，其他的都是直接运行参考题解中的代码。看着自己写的算法得到一个这么大的提升真的很兴奋，算法升级之路哈哈哈，这应该就是算法的魅力了。

5、53. 最大子数组和

5.1、题目描述

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

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

5.2、示例

5.3、提示

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

5.4、个人思考

这道题目也是很简单就能想到使用 DP 来解题，因为同样也是一种不需要记录详细步骤，最终只是要求返回具体的结果数值而已。既然这道题目是可以使用到DP数组，那么思路该怎么进行嘞？先按照常规的思路，尝试能不能找到当前位置与前面获取到的结果有没有什么关系，但是一眼看过去，好像并没有什么很明显的关系。

对于我个人刚开始的时候也在想，因为是求和嘛，所以会不会会进行求和，用上一次的记录与当前元素相加，比对哪个得到的数值大便取哪个。但是很快这种思路便被否决了，因为这种情况对于上面的示例3并不能通过，在示例3中使用这种思路，遇到-1就会重新开始，但事实上最大和是需要加上这个-1的。

那么就需要想，能不能有一个方法，既能解决这个问题，也能够正确的求和得到最大和呢？这时仔细思考之后我们好像需要两个变量分别记录当前求和 sum 与最大求和 max，不断遍历不断对比当前求和能够大于前面记录的最大求和 max，简单想想的话好像这种思路也行得通，那么就尝试一下寻找 DP 里面的三大关键元素：

• DP数组：相对于这里，好像需要使用到的额外变量就只有当前求和 sum 与最大求和 max 两个变量，怎么找不到一个数组嘞？其实这种是进行了一个空间优化的结果，按照常规的话可以使用到一个 一维DP数组，其中用 nums[0] 或 nums[len - 1] 来存放最大和，其余元素位置记录当前位置的求和。而当我们进一步优化时会发现，在这个一维数组中，一共就需要维护存放最大和的元素和存放上一个位置求和的元素两个元素，其余的位置更多的是冗余，因此我们就直接提取出来两个变量代替原有数组，从而进行空间优化。（滚动数组的思想也同样如此）；
• 初始值：这里一共需要给两个变量赋初始值，其中最大求和变量 max = nums[0]，sum = nums[0]，因为开始的第一次时，这两个都等于 nums数组 中的第一个值；
• 关系方程式：这里面核心的就是要解决我们前面提及到的问题：如何确保在遇到可能参与到最大和计算中的负数不被丢弃导致出现错误的结果。我们可以变相的沿用开始思路，我们不用比较当前位置的 sum 与上一次 sum 进行对比，因为这种容易丢弃负数，可以替换成判断 sum 的正负值：
  • 当 sum > 0 时，证明目前元素参与求和时还可能是有正向作用的，即存在使求和增大的可能，这时就可以继续将当前元素与 sum 进行累加；
  • 当 sum < 0 时，证明目前元素肯定是起到负面作用的，这种情况证明当前元素为负数或者上一次计算之后 sum 为负数，那么我们可以直接将当前元素覆盖掉 sum，因为无论当前元素正负与否，相加的结果都会相对变小。

这里对 sum > 0 的情况进一步解释一下，有大聪明可能会想到如果当前元素是负数时，那么直接进行累加可能会使得 sum 越来越小，那会不会得到错误的结果呢？(没错我也是大聪明之一) 不知道大家有没有发现，至今我们还有一个变量 max 没有使用过，而 max 在设定的时候就是为了存放最大值的，因此我们在每次计算 sum 的时候都需要与 max 比对一下大小，负数的时候也要，因为你不知道哪个负数更大。

5.5、代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0 ) {
			return 0;
		} else if (nums.length == 1) {
			return nums[0];
		}
		// 定义最大和
		int max = nums[0];
		// 用于记录循环中求和的数据
		int sum = nums[0];
		// 循环遍历获取最大和
		for (int i = 1; i < nums.length; i++) {
			if (sum > 0) {
				// 当sum还是正数时，进行累加
				sum += nums[i];
			} else {
				// 当sum变成负数时，直接赋值
				sum = nums[i];
			}
			// max对比变化之后的sum，去两者最大值
			max = Math.max(max, sum);
		}
		return max;
    }
}

在写完题解之后好像又想到了，好像这道题目的空间还可以进一步优化，原地操作是可行的。

6、总结

在写了一些DP题型的题目之后，感觉收获还是有的，虽然有时候没有很好的找到三大关键元素，这里就说一下自己是怎么对待这一类题型的，也是为了后面自己回顾，有问题的话欢迎大家提出。

首先是在什么情况下我们可以使用DP进行解题。其实前面有提及到，在这里总结一下，即发现题目最终要求的是一个具体的结果，对具体步骤并不做要求，这种情况下一般都能够使用DP进行题解。从DP的特点出发会发现，DP本来就是将原问题分解成一个个小问题，然后通过计算这些小问题得到一个结果记录下来（记忆化），方便后续的子问题可以拿到之前的结果继续寻找最优解；

其次针对三大关键元素给一些自己的思路。这里大家不要太关注于一定要弄出一个数组来，因为可能自己在第一次想思路的时候就快人一步，优先想到空间优化的方案了。至于怎么寻找这三大关键元素，最核心的应该就是关系方程式：

• DP数组的寻找方法基本上都是一个思想：某个值存放上一次记录结果，某个值存放最优解；
• 初始值一般是根据方程式来推算的，可能DP数组中的第一个值为零或者是 nums数组 的第一个元素；
• 关系方程式其实在写了这么多下来并没有得到一个很好的套路，最好的套路就是经验。(啊你这老六，这不是废话吗！) 不过在写了一些题目之后还是会有一些优先考虑的点，我们在寻找的时候优先找当前元素与上一次的计算结果有没有存在哪些依赖关系，或者需不需要一个额外的空间存放一些特殊的值，比如上面的第五道题目。

最后最后给上一个终极大招，画图。这对于初学者或者是对于没思路的题目真的是打开思路的钥匙，写DP类的题目时，身边一定要有一个本子和笔，不只是可以寻找思路，更是记录当前思路的好帮手。（当然，矿多有平板的伙伴直接用平板也行）。