目录

Leetcode300 最长上升子序列

LeetCode 300 longest-increasing-subsequence

最长上升子序列

LeetCode试题链接
问题描述:
给定一个无序的整数数组,找到其中最长上升子序列(LIS)的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

题解

从一个实例入手,给定输入 [1,3,9,2,4,5]
采用动态规划的方法解题:
表格解释
计算这个序列LIS的过程如下表所示(从左到右,从上到下阅读):

扫描到的数字 LIS长度 对应每个长度所代表的子序列 子序列最后一个元素的数字
1 1 1 1
1,3 2 1
1,3
1
3
1,3,9 3 1
1,3
1,3,9
1
3
9
1,3,9,2 3 1
1,2
1,3,9
1
2
9
1,3,9,2,4 3 1
1,2
1,2,4
1
2
4
1,3,9,2,4,5 4 1
1,2
1,2,4
1,2,4,5
1
2
4
5

文字解释
我们把上述表格的行号记为i,扫描到的数字用数组d[i]表示,即d[1]=[1],d[2]=[1,3],d[3]=[1,3,9]。