题目描述

Given an unsorted array of integers, find the length of longest increasing subsequence.

样例

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. 

算法1

(土味dp)

dp 转移方程 dp[i] = max(dp[j-1]+1,dp[i]) if nums[i] > nums[j] j属于 0…i-1

时间复杂度$O(n^2)$

Python3 代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        dp= [1 for i in range(len(nums))]
        for i in range(1,len(nums)):
            dp[i] = max(dp[j] + 1 if nums[i] > nums[j] else dp[i] for j in range(0,i))
        return max(dp)

算法2

(维护一个最长子数组)

通过bisect二分找到当前要加入的nums[i] 的位置，如果是末尾，说明长度可以加1，如果是中间，则替换掉原来这个位置的数以便以后找到更长的

时间复杂度$O(nlgn)$

python3 代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = []
        for e in nums:
            left = bisect.bisect_left(res,e)
            if left == len(res):
                res.append(e)
            else:
                res[left] = e
        return len(res)