300. Longest Increasing Subsequence（Medium)
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?
方法一：
动态规划，dp[] 代表该位的最长上升子序列最大长度。遍历一遍前面比自己小的数比较就行。
def lengthOfLIS(self, nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
方法二：
二分搜索法，维护一个最大增长的子序列List res，遇到小的数就替换，需要注意的是只是替换并没有改变位数，只有后面的数大于最后一位数res才会增加。
def lengthOfLIS(self, nums):
if not nums:
return 0
res = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > res[-1]:
res.append(nums[i])
else: #binarysearch 只是替换，并没有增加数
l, r, mid = 0, len(res) - 1, 0
while l <= r:
mid = (l + r) // 2
if res[mid] < nums[i]:
l = mid + 1
else:
r = mid - 1
res[l] = nums[i]
print(res)
return len(res)
