MediumLeetCode #300Dynamic Programming

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Constraints

1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4

Examples

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

[2,3,7,101]

Solution

Approach

O(n²) DP: dp[i] = max(dp[j] + 1) for j < i where nums[j] < nums[i]. O(n log n): maintain sorted list of smallest tails and use binary search.

def lengthOfLIS(nums):
    tails = []
    for num in nums:
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num
    return len(tails)

Complexity

Time:O(n log n)

Space:O(n)

Hints

1.Think about what makes a good subsequence
2.For O(n²): dp[i] = longest ending at i
3.For O(n log n): maintain smallest tail for each length

Asked at

Google