[LC] 300. Longest Increasing Subsequence

[seungriyou]

<300. Longest Increasing Subsequence>

Approach

DP 문제로 알려진 LIS 문제이다. 다른 방법으로도 푸는 방법을 알아두자.

Idea 1: DP (O(n^2) Time)

• dp[i] = nums[i]가 포함되는 LIS의 길이

• nums[i]를 볼 때, i 이전의 인덱스인 j를 확인하며

  • nums[i] > nums[j]이고
  • dp[i] < dp[j] + 1 라면

  dp[i]를 dp[j] + 1로 업데이트 한다. (즉, dp[i] = max(dp[i], dp[j] + 1))

def lengthOfLIS(self, nums: List[int]) -> int:
    """
    DP (TC: O(n^2))
        - i 번째 원소를 볼 때, 0 ~ i - 1 번째의 값을 보면서, 가장 큰 값에 + 1
        - dp[i] = nums[i]가 포함되는 LIS의 길이
    """
    n = len(nums)
    dp = [1] * n

    for i in range(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)

Idea 2: Greedy + Binary Search (O(n log(n)) Time) 📌

ref: https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn

다음의 follow-up 조건을 고려하려면 binary search를 적용해야 한다.

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

nums를 순회하면서 가능한 모든 LIS를 구성한다면 성능이 좋지 않을 것이지만, 단 하나의 리스트 lis만 가지고 LIS의 길이를 구할 수는 있다.

이는 현재 확인하고 있는 원소 num이 lis의 마지막 원소보다 크지 않다면(lis[-1] >= num), num을 lis에 덮어씌움으로써 가능하다.

1. 앞에서부터 차례로 lis를 구성한다.
2. 그 과정에서 (1) lis가 비어있거나 (2) 현재 원소 num이 lis의 마지막 원소보다 크다면(lis[-1] < num) lis에 모은다.

3. 그러나 현재 원소 num이 lis의 마지막 원소보다 크지 않다면(lis[-1] >= num), 현재 원소 num을 lis에 덮어쓴다.

   • lis에 덮어쓸 위치를 구하려면, lis에서 num 이상인 값 중에서 가장 작은 값의 위치를 찾으면 된다.
   • lis는 increasing 순서로 구성되어 있으므로 binary search를 사용할 수 있다.

img src

이때, lis가 실제 LIS인 것은 아니며, len(lis)가 가능한 LIS의 길이일 뿐이다.

def lengthOfLIS(self, nums: List[int]) -> int:
    def find_left(lis, num):
        lo, hi = 0, len(lis) - 1

        while lo < hi:
            mid = lo + (hi - lo) // 2
            if lis[mid] < num:
                lo = mid + 1
            else:
                hi = mid

        return lo

    lis = []
    for num in nums:
        # (1) lis가 비어있거나 (2) lis의 마지막 값보다 현재 원소가 큰 경우에는 append
        if not lis or lis[-1] < num:
            lis.append(num)
        # 아니라면 lis에서 num이 들어갈 위치(= num보다 크거나 같은 첫번째 원소) 구하고 덮어쓰기
        else:
            idx = find_left(lis, num)
            lis[idx] = num

    return len(lis)

Complexity

• Time: (idea 1) O(n^2) / (idea 2) O(n log(n))
• Space: O(n)

[seungriyou]

Additional Reference

• Patience Sorting (DP Optimization)
• Java/Python Binary search O(nlogn) time with explanation