Longest Increasing Subsequence

DPGreedyBinary Search
https://leetcode.com/problems/longest-increasing-subsequence

# Solution

Let nn be the length of the array.

The brute force O(n3)O(n^3) solution is omitted.

# Follow Up

Could you come up with the O(n2)O(n^2) solution?

# DP

Let dp[i] be the length of longest increasing subsequence ending with num[i].

The state transition is:
dp[i] = dp[j] + 1 where 0j<i0 \le j < i and num[j] < num[i].

That is, add nums[i] after the LIS in dp[0..i-1].

Complexity

time: O(n2)O(n^2)
space: O(n)O(n)

def lengthOfLIS(self, nums: List[int]) -> int:
    n = len(nums)
    dp = [1 for _ in range(n)]

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1

    return max(dp)
1
2
3
4
5
6
7
8
9
10

Could you improve it to O(nlogn)O(n \log n) time complexity?

To have a longer increasing subsequence, it should increase slower and the append a smaller num.

Maintain a monotonically increasing array gd, where gd[:i] represents the longest increasing subsequence in nums[:i].

When traversing nums, if nums[i] > gd[-1], append nums[i] to the end of gd; o.w., binary search for the first gd[k] where nums[i] > gd[k], and update d[k+1] = nums[i].

Complexity

time: O(nlogn)O(n \log n)
space: O(n)O(n)

def lengthOfLIS(self, nums: List[int]) -> int:
    gd = []

    for num in nums:
        if not gd or num > gd[-1]:
            gd.append(num)
        else:
            left, right = 0, len(gd)-1
            pos = right
            while left <= right:
                mid = (left + right) // 2
                if gd[mid] >= num:
                    pos = mid
                    right = mid - 1
                else:
                    left = mid + 1
            gd[pos] = num

    return len(gd)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19