问题描述：
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
- Follow up: Could you improve it to O(n log n) time complexity?
解法1：时间复杂度 O(n^2)
求一个数组的最长上升子序列。该题的解题思路和 Leetcode 139：将一个字符串划分为字典中的单词 很类似。
使用动态规划：
开辟一个一维数组 dp[len(nums)]，其中，dp[i] 表示以 i 位置结尾的最长上升子序列的长度，最后 max(dp) 就是答案。
对于 i 位置的数字，dp[i] 由之前的 max(dp[j]) (j < i) 决定，并且 nums[j] < nums[i]。为什么呢？因为一旦之前序列的最后一个值 nums[j] 大于等于现在即将变为整个序列最后一个元素 nums[i]，整个序列不再保持上升趋势。所以我们可以通过下列方程表示这个过程：
dp[i] = 1 + max(dp[j] if nums[j] < nums[i]) (j < i)
举例：
nums = [1, 3, 6, 9, 4, 10, 5]，很容易得到 dp[0] = 1，dp[1] = 2，dp[2] = 3, dp[3] = 4。计算 dp[4] 时，遍历 j < 4，发现 nums[3]、nums[2] > nums[4]，不用管继续向前；nums[1] < nums[4]，则说明 nums[4] 可以加入到以数字 3 结尾的最长子序列中，由于数字 3 之前上升子序列最大长度是 dp[1] = 2，则 dp[3] = 1 + max(dp[0], dp[1]) = 3；计算 dp[5] 时，遍历 j < 5，发现 nums[4] < nums[5]，则说明 nums[5] 可以加入到以数字 4 结尾的最长子序列中；发现 nums[3] < nums[5]，则说明 nums[5] 也可以加入到以数字 9 结尾的最长子序列中...；由于之前上升子序列最大长度是 dp[3] = 4，则 dp[4] = 1 + max(dp[0], dp[1], dp[2], dp[3], dp[4]) = 5；之后的数字判断方法也是一样。
时间复杂度 O(N^2)，空间复杂度 O(N)。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lens = len(nums)
if lens == 0 or lens == 1:
return lens
dp = [1] * (lens)
for i in range(1, lens):
maxdp = 1
for j in range(i-1, -1, -1):
if nums[i] > nums[j] and dp[j] >= maxdp:
maxdp = dp[j] + 1
dp[i] = maxdp
return max(dp)
print(Solution().lengthOfLIS([1,3,6,9,4,10,5])) # 5
解法2：时间复杂度 O(n*logn)
参考：最长上升子序列o(nlogn)复杂度一种简单易懂的理解，即使用 lower_bound() 的思想去做。
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lens = len(nums)
if lens == 0:
return 0
dp = [nums[0]]
for i in range(1, lens):
if nums[i] > dp[-1]:
dp.append(nums[i])
else:
dp[bisect.bisect_left(dp, nums[i])] = nums[i]
return len(dp)
