LeetCode #300: Longest Increasing Subsequence

Description:

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solution:

• Method 1: DP (1-d) method

  • Recursive relation: S[i] = S[j] + 1, if S[i]<S[j]+1 and x[j] < x[i].
  • Note that the final solution is max(S[:])
  • Time complexity: O(N^2)
  • Space complexity: O(N)

• Method 2: monotonic sequence (stack)

  • Build a monotonic sequence and inserting the new element with binary search
  • Time complexity: O(N*log(N))
  • Space complexity: O(N)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        else:
            method = 'optim'  # ['simple', 'optim']

            if method == 'simple':
                s = [1 for x in nums]
                for i in range(1, len(nums)):
                    for j in range(i):
                        if s[i] < s[j]+1 and nums[j] < nums[i]:
                            s[i] = s[j] + 1

                return max(s)

            if method == 'optim':
                # monotonic sequence
                seq = [nums[0]]
                for x in nums[1:]:
                    i = self.binary_search(seq, 0, len(seq), x) 
                    if x > seq[-1]: 
                        seq.append(x)
                    else:
                        seq[i] = x
                return len(seq)

    def binary_search(self, array, start, end, x):
        if start >= end:
            return int(start)
        else:
            mid = int( (start + end)/2 )
            if array[mid] < x:
                return self.binary_search(array, mid+1, end, x)
            else:
                return self.binary_search(array, start, mid, x)