lis

Longest Increasing Subsequence Problem

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

• Equivalent to longest northeast problem (in computational-geometry)
• Resources
  • Longest Increasing Subsequence (LIS) | GeeksforGeeks
  • Longest increasing subsequence | Wikipedia
  • Longest increasing subsequence | Algorithms for Competitive Programming
• Procedure (handwritten note)
  • Start from initial point $s$, use sweeping method.
  • Find the first point that forms a increasing sub-sequence, mark it with number 1.
  • Upon finding another point, if it extends from the previous point on path, mark it with number 2, and keep a pointer to the previous point on path.
  • Upon finding a lower point that can be used to form a path with length of 2, insert it into our state, and delete all the previous one that are higher. They’re no longer useful anyway.

Approach 1: DP

• dp[i] represents the length of LIS that ends at i.
• dp[0] = 1 as base condition.
• For each nums[j] before nums[i], if that element is smaller than nums[i], we can extend dp[i] to dp[j] + 1 (if it’s indeed larger) using nums[j] -> nums[i].
• Repeat the process.

n = len(nums)
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j] + 1)
return max(dp)

• Time complexity: $O(n^2)$

Approach 2: Intelligently Building Subsequence

• If the num is greater the sub[-1], just append it to extend the subsequence.
• Otherwise, iterate through sub and find the first element that is greater than num, and replace them.
• The idea is, replacing this number allows future num’s encountered to be also included to extend the subsequence.
• The resulting subsequence is not a valid one, but the length of it matches LIS.

sub = [nums[0]]
 
for num in nums[1:]:
    if num > sub[-1]:
        sub.append(num)
    else:
        i = 0
        while num > sub[i]:
            i += 1
        sub[i] = num
 
return len(sub)

• Time complexity: $O(n^2)$

Approach 3: Subsequence Building with binary-search

For bisect_left, all(elem < x for elemin a[lo : ip]).

sub = []
for num in nums:
    i = bisect_left(sub, num)
    if i == len(sub):
        sub.append(num)
    else:
        sub[i] = num
return len(sub)

Time complexity: $O(n\lg n)$.