300_ Longest Increasing Subsequence

[Medium][Dynamic Programming, Binary Search]

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.

Solution 1:

Idea:

• If we know the lengths of longest increasing subsequence that end at indices 0, 1, 2, n-1, and we want to know the longest increasing subsequence that ends at index n, what shall we do?

  • We should look for look for the longest subsequence ending at any indices 0, 1, 2, n-1 whose value is less than the value at index n. Then this max length plus one will be the answer.

  • If there is no values in front of index n that is less than value at index n, the max length at index n is 1.

  • The max length for the entire array is the max of max length at all the indices.

• Can be written in iterative or recursive fashion.

Time Complexity: $O(n^2)$

Space Complexity: $O(n)$

Iterative:

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    output = [1] * len(nums)

    for i in range(1, len(nums)):
        output[i] = 1 + max([output[j] for j in range(i) if nums[j] < nums[i]] + [0])
        # [0] is for nothing from nums[j] is less than nums[i]
        # parameter inside max() can't be empty

    return max(output + [0])  # [0] is for empty nums

Recursive: (slow)

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def helper(i):
        if i < 0:
            return
        elif i == 0:
            output[i] = 1
        elif output[i] == 0: 
            output[i] = 1 + max([helper(j) for j in range(i) if nums[j] < nums[i]] + [0])
        return output[i]

    output = [0] * len(nums)
    for i in range(len(nums)-1, -1, -1):
        helper(i)
    return max(output + [0])

Solution 2:

Idea:

• Our strategy determined by the following conditions:

  • If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.

  • If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].

  • If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

• Note that at any instance during our construction of active lists, the following condition is maintained.

  • “end element of smaller list is smaller than end elements of larger lists”.

• Refer to here

Time Complexity: $O(n\log{n})$

Space Complexity:

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def CeilIndex(A, l, r, key): 

        while (r - l > 1): 

            m = l + (r - l)//2
            if (A[m] >= key): 
                r = m 
            else: 
                l = m 
        return r 

    def LongestIncreasingSubsequenceLength(A, size): 

        # Add boundary case, 
        # when array size is one 

        tailTable = [0 for i in range(size+1)] 
        len=0 # always points empty slot 

        tailTable[0] = A[0] 
        len = 1
        for i in range(1, size): 

            if (A[i] < tailTable[0]): 

                # new smallest value 
                tailTable[0] = A[i] 

            elif (A[i] > tailTable[len-1]): 

                # A[i] wants to extend 
                # largest subsequence 
                tailTable[len] = A[i] 
                len+=1

            else: 
                # A[i] wants to be current 
                # end candidate of an existing 
                # subsequence. It will replace 
                # ceil value in tailTable 
                tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i] 


        return len

    return 0 if not nums else LongestIncreasingSubsequenceLength(nums, len(nums))