Longest Increasing Subsequence

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

Approach

O(N^2) Solution

To find the length of the longest strictly increasing subsequence in an integer array nums, we can use the dynamic programming approach. Here’s how it works:

  1. We create an array dp of the same length as nums, where dp[i] represents the length of the longest increasing subsequence that ends at index i.
  2. We initialize each element of dp to 1 because the longest increasing subsequence that ends at index i must contain at least the element at index i itself.
  3. For each index i from 1 to n-1 where n is the length of nums, we compare nums[i] with all the elements before it, that is, from 0 to i-1. If nums[i] is greater than nums[j], where 0 <= j < i, then we can include nums[i] in the longest increasing subsequence that ends at index i, which would have a length of dp[j]+1. We update dp[i] to the maximum of all such values.
  4. Finally, we return the maximum value in the dp array as the length of the longest strictly increasing subsequence in the nums array.

Here’s the Python code that implements the above approach:

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * 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)

Example

>>> nums = [10,9,2,5,3,7,101,18]
>>> lengthOfLIS(nums)
4

In the above example, the longest strictly increasing subsequence is [2, 3, 7, 101], which has a length of 4.


O(N log N) Solution

To improve the time complexity of the dynamic programming approach to O(n log n), we can use a modified version of the binary search algorithm.

Here’s the modified algorithm:

  1. We create an empty array tails of length n, where n is the length of nums. tails[i] represents the smallest tail element of all increasing subsequences of length i+1 that we have found so far.
  2. We initialize tails[0] to be the first element of nums.
  3. For each element num in nums starting from index 1, we perform a binary search in the tails array to find the largest index i such that tails[i] is less than or equal to num.
  4. If we find such an index i, we update tails[i] to be num, as we have found a longer increasing subsequence of length i+1.
  5. If we do not find such an index i, it means that num is greater than all the elements in the tails array, and we can append num to the end of the tails array to create a new longest increasing subsequence of length i+1.
  6. Finally, we return the length of the tails array as the length of the longest strictly increasing subsequence in the nums array.

Here’s the Python code that implements the above algorithm:

def lengthOfLIS(nums):
    n = len(nums)
    tails = [0] * n
    size = 0
    for num in nums:
        left, right = 0, size
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        tails[left] = num
        size = max(size, left + 1)
    return size

nums = [10,9,2,5,3,7,101,18]
print(lengthOfLIS(nums)) # Output: 4

In the above example, the longest strictly increasing subsequence is [2, 3, 7, 101], which has a length of 4. The time complexity of this algorithm is O(n log n).