动态规划 —— 最长递增子序列（LIS）

LIS：Longest Increasing Subseq，最长递增子序列，是不要求该子序列在原始序列中间连续存放的。

为了降低对这一问题的理解难度，既然最长递增子序列不要求子序列位置连续，我们不妨先考虑这样一种情况，即求连续的递增子序列的长度，如果前一位的值，小于当前位，则当前为的连续递增子序列的长度为前一位的加1；

def sis(seq):l = len(seq)L = [1]*lfor i in range(1, l):if seq[i-1] <= seq[i]:L[i] = 1+L[i-1]return max(L)

回过头来，我们继续看稍微复杂一丢丢的 LIS 问题。如果我们已经知道了前面 k 位子序列的方法，会不知道如何找出 k+1 位的子序列吗？一旦问题抽象出这样一种结构，答案其实就已经显见了，也即我们只需看当前元素之前的元素是否都小于当前元素即可，小于则加1，再取最值即可。

def lis(seq):l = len(seq)L = [1]*lfor i in range(l):for j in range(i):if seq[j] <= seq[i]:L[i] = max(L[i], 1+L[j])return max(L)