废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【动态规划】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
连续子数组的最大和【MID】
来从动态规划最简单的题开始训练
题干
题干中可以提炼的关键信息：连续的子数组，整数有正有负，求连续子数组的最大和，题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决
解题思路
按照动态规划的思路进行状态设计和状态转移方程编写
1 定义状态（定义子问题）
dp[i]：表示以 nums[i] 结尾的连续子数组的最大和。说明：「结尾」和「连续」是关键字。
2 状态转移方程（描述子问题之间的联系）
根据状态的定义，由于 nums[i] 一定会被选取，并且以 nums[i] 结尾的连续子数组与以 nums[i - 1] 结尾的连续子数组只相差一个元素 nums[i] 。假设数组 nums 的值全都严格大于 0，那么一定有 dp[i] = dp[i - 1] + nums[i]。可是 dp[i - 1] 有可能是负数，于是分类讨论：
- 如果
dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组； - 如果
dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]。
以上两种情况的最大值就是 dp[i] 的值，写出如下状态转移方程：
3 初始化状态
dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
这里的dp[i]只是以i为结尾的连续子数组的最大和，并不是题目中的问题，数组的连续子数组最大和，所以最终解并不是子问题的解，需要用一个MAX值承载，通过与dp[i]比较更新最终解
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型 */ public int FindGreatestSumOfSubArray (int[] array) { // 1 定义dp数组，初始化状态,初始化最终解 int[] dp = new int[array.length]; dp[0] = array[0]; int greatSum = dp[0]; // 2 定义状态转移方程 for (int i = 1; i < array.length; i++) { // 状态转移方程，求解当前的dp[i] dp[i] = dp[i - 1] <= 0 ? array[i] : dp[i - 1] + array[i]; // 更新最大值 greatSum = Math.max(greatSum, dp[i]); } return greatSum; } }
复杂度分析
时间复杂度：遍历了一遍数组，所以时间复杂度为O（N）
空间复杂度：定义了动规数组，空间复杂度为O（N）
乘积最大子数组【MID】
处理一个合连续子数组的最大和类似的题目，乘积最大的子数组
题干
解题思路
原题解地址，数组的动态规划问题、子序列、连续子序列的一个常见的状态定义是：
以下标 i 结尾的连续子序列的乘积的最大值。
最后把整个 dp 数组看一遍求最大值即可。因此状态转移方程可能是：
dp[i] = max(dp[i - 1] * nums[i], nums[i])
说明：牢记状态的定义，一定以下标 i 结尾，即：乘积数组中 nums[i] 必须被选取，但是nums[i]可能是正数也可能是负数
- 如果nums[i] 是负数，要想获得最大乘积，则dp[i-1]越小则dp[i]越大，于是我们可能就需要记录一下**dp[i-1]**的那个最小数。
- 如果nums[i] 是正数，则取上一个状态的最大值*
所以要维护两个动态规划数组
1 定义状态（定义子问题）
maxDp[i]：表示以 nums[i] 结尾的连续子数组的最大乘积。说明：「结尾」和「连续」是关键字。
minDp[i]： 表示以 nums[i] 结尾的连续子数组的最小乘积。说明：「结尾」和「连续」是关键字。
2 状态转移方程（描述子问题之间的联系）
if (nums[i] >= 0) { // 如果当前值为正数，则最大值为 Math.max(nums[i], maxDp[i - 1] * nums[i]),因为maxDp[i-1]可能为负数，这样不如舍弃重新开始 maxDp[i] = Math.max(nums[i], maxDp[i - 1] * nums[i]); // 同时需要更新最小值，nums[i]为正值，所以就用最小乘积，minDp[i - 1] * nums[i]更小 minDp[i] = Math.min(nums[i], minDp[i - 1] * nums[i]); } else { // 如果当前值为负数，则最大值为Math.max(nums[i], minDp[i - 1] * nums[i])，minDp[i - 1]可能为负数，这样不如使用minDp[i - 1] * nums[i], maxDp[i] = Math.max(nums[i], minDp[i - 1] * nums[i]); // 同时需要更新最小值，nums[i]为负值，所以就用最大乘积，maxDp[i - 1] * nums[i]更小 minDp[i] = Math.min(nums[i], maxDp[i - 1] * nums[i]); }
3 初始化状态
// base case 初始状态为数组的第一个元素 maxDp[0] = nums[0]; minDp[0] = nums[0]; int ans = nums[0];
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
最终解采用实时更新的方式
// 更新整体最大值 ans = Math.max(ans, maxDp[i]);
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @return int整型 */ public int maxProduct(int[] nums) { // 1 入参合法性判断 if (nums == null || nums.length == 0) { return 0; } // 2 定义两个动态规划数组，分别记录以i为结尾的最大乘积子数组,并维护最大乘积值 int[] maxDp = new int[nums.length]; int[] minDp = new int[nums.length]; // 3 base case 初始状态为数组的第一个元素 maxDp[0] = nums[0]; minDp[0] = nums[0]; int ans = nums[0]; // 4 状态转移方程 for (int i = 1; i < nums.length; i++) { if (nums[i] >= 0) { // 如果当前值为正数，则最大值为 Math.max(nums[i], maxDp[i - 1] * nums[i]),因为maxDp[i-1]可能为负数，这样不如舍弃重新开始 maxDp[i] = Math.max(nums[i], maxDp[i - 1] * nums[i]); // 同时需要更新最小值，nums[i]为正值，所以就用最小乘积，minDp[i - 1] * nums[i]更小 minDp[i] = Math.min(nums[i], minDp[i - 1] * nums[i]); } else { // 如果当前值为负数，则最大值为Math.max(nums[i], minDp[i - 1] * nums[i])，minDp[i - 1]可能为负数，这样不如使用minDp[i - 1] * nums[i], maxDp[i] = Math.max(nums[i], minDp[i - 1] * nums[i]); // 同时需要更新最小值，nums[i]为负值，所以就用最大乘积，maxDp[i - 1] * nums[i]更小 minDp[i] = Math.min(nums[i], maxDp[i - 1] * nums[i]); } // 更新整体最大值 ans = Math.max(ans, maxDp[i]); } return ans; } }
复杂度分析
时间复杂度：遍历了一遍数组，所以时间复杂度为O（N）
空间复杂度：定义了动规数组，空间复杂度为O（N）
最长递增子序列【MID】
终于又来到一道看了很久的高频题目这里
题干
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的
解题思路
按照动态规划的思路进行状态设计和状态转移方程编写，这里用数学归纳法进行状态转移公式的推导。
数学归纳法：比如我们想证明一个数学结论，那么我们先假设这个结论在 k < n 时成立，然后根据这个假设，想办法推导证明出 k = n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立
我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0...i-1] 都已经被算出来了，然后问自己：怎么通过这些结果算出 dp[i]
1 定义状态（定义子问题）
我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度，这个定义中 nums[i] 必须被选取，且必须是这个子序列的最后一个元素；
2 状态转移方程（描述子问题之间的联系）
算法演进过程中每个 dp[i] 的结果是我们肉眼看出来的，我们应该怎么设计算法逻辑来正确计算每个 dp[i] 呢？这就是动态规划的重头戏，如何设计算法逻辑进行状态转移，才能正确运行呢？这里需要使用数学归纳的思想：
假设我们已经知道了 dp[0…4] 的所有结果，我们如何通过这些已知结果推出 dp[5] 呢
根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到这些子序列末尾，就可以形成一个新的递增子序列，而且这个新的子序列长度加一
- nums[5] 前面有哪些元素小于 nums[5]？这个好算，用 for 循环比较一波就能把这些元素找出来。
- 以这些元素为结尾的最长递增子序列的长度是多少？回顾一下我们对 dp 数组的定义，它记录的正是以每个元素为末尾的最长递增子序列的长度
以我们举的例子来说，nums[0] 和 nums[4] 都是小于 nums[5] 的，然后对比 dp[0] 和 dp[4] 的值，我们让 nums[5] 和更长的递增子序列结合，得出 dp[5] = 3
for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } }
3 初始化状态
根据这个定义，我们就可以推出 base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己
4 求解方向
这里采用自底向上，从最小的状态开始求解
5 找到最终解
根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值
int res = 0; for (int i = 0; i < dp.length; i++) { res = Math.max(res, dp[i]); } return res;
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; class Solution { // 最长上升子序列 public int lengthOfLIS(int[] nums) { // 1 入参校验判断 if (nums.length < 1) { return -1; } // 2 定义DP数组：dp[i]表示以nums[i]为结尾的上升子序列的最大长度 int[] dp = new int[nums.length]; // 3 base case, 所有元素都至少包含自己，且dp[0]=1 因为只有一个元素,二者合并 Arrays.fill(dp, 1); // 4 状态转移，填充状态转移表 for (int i = 1; i < nums.length; i++) { // dp[i]为i之前的小于nums[i]的所有dp[i]的最大值组成 for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // 5 最终解为dp数组的最大值 int result = 0; for (int i = 0; i < dp.length; i++) { result = Math.max(result, dp[i]); } return result; } }
当然最值的更新也可以在双重循环中同步进行
import java.util.*; class Solution { // 最长上升子序列 public int lengthOfLIS(int[] nums) { // 1 入参校验判断 if (nums.length < 1) { return -1; } // 2 定义DP数组：dp[i]表示以nums[i]为结尾的上升子序列的最大长度 int[] dp = new int[nums.length]; // 3 base case, 所有元素都至少包含自己，且dp[0]=1 因为只有一个元素,二者合并 Arrays.fill(dp, 1); // 4 状态转移，填充状态转移表 int result = 1; for (int i = 1; i < nums.length; i++) { // dp[i]为i之前的小于nums[i]的所有dp[i]的最大值组成 for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } result = Math.max(result, dp[i]); } return result; } }
复杂度分析
时间复杂度：O(N^2)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；
空间复杂度：O(N)，要使用和输入数组长度相等的状态数组，因此空间复杂度是 O(N)。
