0300 Longest Increaseing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
 

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

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

• Dynamic programming solves this problem in \(O(n^2)\)

• Binary search can be used here to perform \(O(n^2)\) operations.

def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)


# test on typical cases
print(lengthOfLIS([10,9,2,5,3,7,101,18]))
print(lengthOfLIS([1,3,6,7,9,4,10,5,6]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9]))
print(lengthOfLIS([9,8,7,6,5,4,3,2,1]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9]))

4
6
9
1
9

# use binary search within patience sort
def lengthOfLIS(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    # top of each pile in the patience sort
    # dp is sorted in ascending order
    dp = [nums[0]]
    for i in range(1, len(nums)):
        if nums[i] > dp[-1]:
            dp.append(nums[i])
        else:
            # binary search to find the leftmost element (smallest) in piles that is larger than nums[i]
            l, r = 0, len(dp)-1
            while l <= r:
                mid = (l+r)//2
                # move right
                if dp[mid] < nums[i]:
                    l = mid + 1
                # move left
                else:
                    r = mid - 1
            dp[l] = nums[i]
    return len(dp)

# test
print(lengthOfLIS([10,9,2,5,3,7,101,18]))
print(lengthOfLIS([1,3,6,7,9,4,10,5,6]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9]))
print(lengthOfLIS([9,8,7,6,5,4,3,2,1]))
print(lengthOfLIS([1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9]))

4
6
9
1
9