【算法训练-动态规划 二】【线性DP问题】最长递增子序列

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

复杂度分析

时间复杂度：遍历了一遍数组，所以时间复杂度为O（N）
空间复杂度：定义了动规数组，空间复杂度为O（N）

乘积最大子数组【MID】

处理一个合连续子数组的最大和类似的题目，乘积最大的子数组

题干

解题思路

原题解地址，数组的动态规划问题、子序列、连续子序列的一个常见的状态定义是：

以下标 i 结尾的连续子序列的乘积的最大值。

最后把整个 dp 数组看一遍求最大值即可。因此状态转移方程可能是：

dp[i] = max(dp[i - 1] * nums[i], nums[i])
1

说明：牢记状态的定义，一定以下标 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]);
 }
1
2
3
4
5
6
7
8
9
10
11
12

3 初始化状态

// base case 初始状态为数组的第一个元素
maxDp[0] = nums[0];
minDp[0] = nums[0];
int ans =  nums[0];
1
2
3
4

4 求解方向

这里采用自底向上，从最小的状态开始求解

5 找到最终解

最终解采用实时更新的方式

// 更新整体最大值
ans = Math.max(ans, maxDp[i]);
1
2

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无

其中数据结构、算法和技巧分别来自：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

复杂度分析

时间复杂度：遍历了一遍数组，所以时间复杂度为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);
    }
}

1
2
3
4
5
6

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;

1
2
3
4
5
6

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无

其中数据结构、算法和技巧分别来自：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

当然最值的更新也可以在双重循环中同步进行

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

复杂度分析

时间复杂度：O(N^2)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；

空间复杂度：O(N)，要使用和输入数组长度相等的状态数组，因此空间复杂度是 O(N)。