# 最长上升子序列（LIS） 在计算机科学中，**最长递增子序列**（**longest increasing subsequence**）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论、表示论相关的研究都会涉及最长递增子序列。 ## 例子 对于以下的原始序列 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 最长递增子序列为 0, 2, 6, 9, 11, 15. 值得注意的是原始序列的最长递增子序列并不一定唯一，对于该原始序列，实际上还有以下两个最长递增子序列 0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15 ## 分析 以[Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)为例，对于序列`a`，如果定义`f[i]`表示以`a[i]`结尾的序列的最长长度，可以得到： 1. 状态：f[i] 表示以i结尾的序列的最长长度。 2. 转移方程：f[i] = max(f[j] + 1),(j < i 且 a[i] > a[j])。 3. 初始化：f[i] = 1，(1 <= i <= n)。 4. 答案：max(f)。 代码如下： ~~~python class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 f = [1 for i in range(n)] for i in range(1, n): for j in range(i): if nums[i] > nums[j]: f[i] = max(f[i], f[j] + 1) return max(f) ~~~