[LeetCode] 300. Longest Increasing Subsequence

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

DP Solution

Let DP[i] = longest increasing sequence end at i, then DP[i] = DP[j] + 1 if Nums[i] > Nums[j]

Time Complexity = O ( N ** 2 )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        N = len(nums)
        dp = [1] * N
        
        for i in range(1, N):
            for j in reversed(range(i)):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
        
        return max(dp)

DP + Binary Search Solution

DP is a cache to store the increasing sequence.

Iterate the input array and pick number from left to right to insert into DP.

lowerBound method returns the position of the newly added number should be inserted into DP to maintain an increasing sequence.  Replace existing number if the returned position does not expand DP. Otherwise, append the new number to DP.

The final length of DP is the length of the longest increasing subsequence.  However, DP is not the longest increasing subsequence.

Time Complexity = O ( N * LogN )

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        def lowerBound(nums, n):
            """
            return the first position from left where nums[i] <= n
            return 0 if all items in nums > n
            return len(nums) if all items in nums < n
            """
            
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if nums[mid] == n:
                    right = mid
                elif nums[mid] < n:
                    left = mid + 1
                elif nums[mid] > n:
                    right = mid
                
            return left
        
        
        dp = []
        
        for n in nums:    
            i = lowerBound(dp, n)
            if i == len(dp):
                dp.append(n)
            else:
                dp[i] = n
        
        return len(dp)

Use built-in binary-search lib:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        
        for n in nums:
            i = bisect.bisect_left(dp, n)
            if i == len(dp):
                dp.append(n)
            else:
                dp[i] = n
        
        return len(dp)

Edited on 02/06/2021. Add implementation with built-in binary search lib.