leetcode-greedy

300. Longest Increasing Subsequence.py

class Solution:
    """    
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative?
            duplicates? -> yes
            strictly increasing?  means [2,5,5] won't count as valid LIC
            
    Thought Process
        DP:
        If we traverse the given nums, whether current subsequence is a valid depends on whether previous subsequence is valid. So, there must be lots of overlapping subproblems.
        
        Let's define subproblems dp[i]: length of increasing subsequence end with ith element
        
        So, our goal is return max(dp[0], dp[1],.., dp[n-1]) instead of dp[n-1]
        
        base case, i == 0
            dp[0] = 1
            
        if cuurent subproblems relies on all previoust subproblems.
             if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
                u don't know which subproblem dp[j] will contribute dp[i] the max lengh of increasing subsequence
                so you take maximum always.
                
        [1,2,3,4,5]
           i
         j
             i
         j j
         
        Binary Search + Greedy
            Step1: 
                We maintain a dynamic increasing subsequence array, called LIC.
                Initially, it's empy list.
            
            Step2:
                Traverse the whole array.
                For each num, we search where to insert current num into LIC to have LIC atm.
                Note, here we use left bound to find where to insert current num into LIC.
                The reason why we use lower bound is. There's duplicate in give num and [2,5,5] won't count as valid LIC, for example. 
            step3:
                return len(LIC)
    Note:
        1.bisect.bisect_left returns the leftmost place in the sorted list to insert the given element. 
        2.bisect.bisect_right returns the rightmost place in the sorted list to insert the given element.     
    """
    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        DP
        """
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        dp = [1 for _ in range(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)
    
    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        BS
        T: O(nlogn). because Binary search takes O(logn) and it is called n times
        S: O(n)
        """
        lic = [] # res array is meant to store the increasing subsequence formed by including the currently encountered element 
        for num in nums:
            # binary search: to find where to insert current num into our LIC
            #left = bisect.bisect_left(res,e)
            left = self.find_lower_bound(lic, num)
            if left == len(lic):
                # the coming element larger than all elements in res, it means we need to update the len = len + 1
                lic.append(num)
            else:
                lic[left] = num
            print (lic)
        print (lic)
        return len(lic)
    
    def find_lower_bound(self, nums, target):
        """
        the reason we use lower bound unless added current num is larger than all elements in the current LIC,
        we won't increase length of LIC.
        For example, 
        LIC = [2,5]
        added cuurent num is 5
        The LIC is still [2,5]
        nums:LIC
        target: added current num
        
        Note: 
            LIC won't guarantee it's correct solution.
            For example, given [10,9,2,5,0]
            LIC in the end, would be [0, 5], should be [2, 5]
            but len(LIC) is still 2
        """
        l, r = 0, len(nums)
        while l < r:
            m = l + (r-l) // 2
            if nums[m] >= target:
                r = m
            else:
                l = m+1
        return l