最长上升子序列题解

Posted on Edited on In Disqus: Symbols count in article: 1.5k Reading time ≈ 1 mins.

最长上升子序列 是一个经典的动态规划题目：

1
2
3
4
5
6
7
8
9
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
   输入: [10,9,2,5,3,7,101,18]
   输出: 4 
   解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
   说明:
       可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
       你算法的时间复杂度应该为 O(n2) 。
   进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解决 DP 问题在之前的 文章 提过，我们可以先通过最简单的例子（实例）找到规律，在将规律范化（抽象），因为我们的大脑习惯思考具体的东西。

以题目中的示例来分析：

无序整数数组 上升子序列 最大上升子序长度
10 10 1
10, 9 10

9		 1
10, 9, 2 10
9

2		 1
10, 9, 2, 5 10
9
2

2, 5		 2
10, 9, 2, 5, 3 10
9
2
2, 5

2, 3		 2
10, 9, 2, 5, 3, 7 10
9
2
2, 5
2, 3

2, 7
2, 5, 7
2, 3, 7		 3
10, 9, 2, 5, 3, 7, 101 10
9
2
2, 5
2, 3
2, 7
2, 5, 7
2, 3, 7

10, 101
9, 101
2, 101
2, 5, 101
2, 3, 101
2, 7, 101
2, 5, 7, 101
2, 3, 7, 101		 4
10, 9, 2, 5, 3, 7, 101, 18 10
9
2
2, 5
2, 3
2, 7
2, 5, 7
2, 3, 7
10, 101
9, 101
2, 101
2, 5, 101
2, 3, 101
2, 7, 101
2, 5, 7, 101
2, 3, 7, 101

10, 18
9, 18
2, 18
2, 5, 18
2, 3, 18
2, 7, 18
2, 5, 7, 18
2, 3, 7, 18		 4

根据上述的穷举，我们发现在 “无序整数数组” 中每添加一个元素，就是根据上一次的 “上升子序列” 结果中找出结尾比当前元素小的情况，追加当前元素。 10, 9, 2, 5, 3, 7 的 “上升子序列” 就是在 10, 9, 2, 5, 3 的子序结果中找到结尾比 7 小的子序结果 [2][2,5][2,3] 追加上 7 的结果 [2,7][2,5,7][2,3,7]。

根据这个规律，我可以定义状态，d(i) 表示以第 i 个数组结尾的最长递增子序列的长度。 最长递增子序列长度需要根据[d(0), d(i - 1)] 的结果计算，状态方程是：dp[i] = max(dp[j])+1 (0 ≤ j < i & num[j] < num[i]) ，最终结果是 max(dp[i])。

这个题目的特点是，计算当前层的 DP 结果需要遍历之前所有的 DP 结果找到最值，才能确定当前层的结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lengthOfLIS(int[] nums) {
    if (null == nums || nums.length == 0) {
        return 0;
    }
    int[] d = new int[nums.length];
    d[0] = 1;
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        int cur = 0;
        // 计算 0 ~ i 中子序最长
        for (int j = 0; j < i; j++) {
            // nums[i] > nums[j], 则 nums[i] 可追加到原来 d[j] 的结果中
            if (nums[i] > nums[j]) {
                cur = Math.max(cur, d[j] + 1);
            } else { // 否则, nums[i] 自成一个序列
                cur = Math.max(cur, 1);
            }
        }
        d[i] = cur;
        max = Math.max(max, d[i]);
    }
    return max;
}