LC 300. LIS

Description

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?

Analysis

This is a very classical problem —— LIS.

We can use two methods to deal with it.

1. DP

dp[i] means the length of LIS ended with nums[i]

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # O(n^2), dp
        res, n = 0, len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i - 1, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])
        return res

2. Bisect Search

We can traverse very number in nums, and meanwhile, update LIS array.

If we find that there is no number in LIS larger than current number, append the current number; otherwise, replace the nums[idx] with current number, it might not be LIS at present, however, the length of LIS will not change and we get the possibility to get longer LIS in the future because we replaced a bigger number with a smaller one.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # O(nlogn), bisect search
        res = [float('inf')]
        for num in nums:
            idx = bisect.bisect_left(res, num)
            if idx == len(res): res.append(num)
            else: res[idx] = num
        return len(res) if res[0] != float('inf') else 0