给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。
样例 样例 1: 输入: [5,4,1,2,3] 输出: 3
解释: LIS 是 [1,2,3]样例 2: 输入: [4,2,4,5,3,7] 输出: 4
解释: LIS 是 [2,4,5,7]挑战 要求时间复杂度为O(n^2) 或者 O(nlogn)
说明 最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。 https://en.wikipedia.org/wiki/Longest_increasing_subsequence
分析 a [ i ] a[i] a[i]表示以元素 n u m s [ i ] nums[i] nums[i]结尾的子数组的最长递增序列的长度，然后求出数组a的最大值即可，初始化数组a为1，对以 n u m s [ i ] nums[i] nums[i]结尾的子数组，j从0到i-1遍历，找到一个比他小的就+1
状态转移方程 { a [ 1 ] = 1 a [ i ] = max 1 ≤ j < i n u m s [ j ] ⩽ n u m s [ i ] { n u m s [ j ] } + 1 ( 1 ⩽ i ⩽ n ) \left\{\begin{array}{l}{a[1]=1} \\ {a[i]=\max _{1 \leq j<i \atop nums[j] \leqslant nums[i]}\{nums[j]\}+1 \quad(1 \leqslant i \leqslant n)}\end{array}\right. {a[1]=1a[i]=maxnums[j]⩽nums[i]1≤j<i{nums[j]}+1(1⩽i⩽n) 表示在 n u m s [ i ] nums[i] nums[i]前面找满足 n u m s [ j ] < n u m s [ i ] nums[j]<nums[i] nums[j]<nums[i] ( 1 ⩽ j ⩽ i ) (1 \leqslant j \leqslant i) (1⩽j⩽i)的最大的 a [ j ] a[j] a[j]， 则以 n u m s [ i ] nums[i] nums[i]为结尾的最长递增子序列的长度就是 a [ j ] + 1 a[j]+1 a[j]+1
class Solution: """ @param nums: An integer array @return: The length of LIS (longest increasing subsequence) """ def longestIncreasingSubsequence(self, nums): # write your code here n = len(nums) if n<=1: return 0 a = [0 for _ in range(n)] for i in range(n): a[i] = 1 for j in range(0, i): if nums[j] < nums[i]: a[i] = max(a[i], a[j]+1) return max(a)