标签：元素 详解 LIS 序列 长度 最长 dp
最长上升子序列(LIS):
定义:
最长上升子序列（LIS）是一个序列中，找到一个子序列，使得这个子序列的元素是严格递增的，且该子序列的长度最大
*子串和子序列的差别:
子串: 元素的连续性，必须是相邻的
子序列:元素的相对顺序，可以不连续
从实例中来
[1, 7, 5, 6, 9, 2, 4] 这个数组根据肉眼扫描法不难发现出LIS是[1, 5, 6, 9]长度最长为4
对于这个长度如何求解出来, 有着这几个经典解法去求解
解法1:
动态规划 复杂度O(n ^ 2)：
在计算LIS的最长长度的时候, 某些元素a[i]是LIS的一部分, 那么a[i]以前的, 元素所有小于a[i]的元素所构成的LIS的长度就是最优的 对于动态规划来说, 为了避免
重复问题的重复计算, 可以缓存下dp[i]当前的值, dp[i]储存的就是a[i]为结尾的最长长度, 那么这个序列的最长长度只需去求当前dp[i]数组的最大值即可
标签：元素,
详解,
LIS,
序列,
长度,
最长,
dp
From： https://www.cnblogs.com/iters/p/18444395