Longest Increasing Subsequence

Problem

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

Naive Approach (Brute Force)

A brute-force approach would involve generating all possible subsequences of the input array and then checking each subsequence to see if it is strictly increasing. We would then keep track of the longest increasing subsequence found so far.

1. Generate all subsequences: Iterate through the array and, for each element, decide whether to include it in the current subsequence or not. This can be done using recursion or bit manipulation.
2. Check for increasing order: For each generated subsequence, check if it is strictly increasing. If it is not, discard it.
3. Track the longest: Keep track of the length of the longest increasing subsequence found so far.

Complexity:

• Time Complexity: O(2ⁿ * n), where n is the length of the input array. Generating all subsequences takes O(2ⁿ) time, and checking if a subsequence is increasing takes O(n) time in the worst case.
• Space Complexity: O(n) in the worst case due to the space used by the recursion stack or to store a subsequence.

Optimal Approach (Dynamic Programming)

We can solve this problem more efficiently using dynamic programming. Let dp[i] be the length of the longest increasing subsequence ending at index i.

1. Initialization: Initialize dp[i] to 1 for all i, because the minimum length of an increasing subsequence ending at i is 1 (the element itself).
2. Iteration: Iterate through the array nums from left to right. For each element nums[i], iterate through all the elements before it (nums[j] where j < i).
   • If nums[i] > nums[j], it means we can extend the longest increasing subsequence ending at j by including nums[i]. So, we update dp[i] to max(dp[i], dp[j] + 1). This step means that we check if adding the current element would give us a longer increasing subsequence than what we currently have.
3. Result: After iterating through the entire array, the maximum value in the dp array will be the length of the longest increasing subsequence.

Complexity:

• Time Complexity: O(n²), where n is the length of the input array. This is because we have nested loops.
• Space Complexity: O(n), for the dp array.

Edge Cases:

• Empty array: If the input array is empty, the length of the longest increasing subsequence is 0.
• Array with one element: If the input array has only one element, the length of the longest increasing subsequence is 1.
• Array with all elements the same: If all elements in the array are the same, the length of the longest increasing subsequence is 1.
• Array in strictly decreasing order: the longest increasing subsequence is of length 1.

def lengthOfLIS(nums):
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # Initialize dp array with 1

    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)

Follow-up: O(n log n) Solution:

It is possible to improve the time complexity to O(n log n) using a combination of binary search and dynamic programming. This approach involves maintaining a "tails" array, where tails[i] is the smallest tail of all increasing subsequences of length i+1. Then we iterate through the input nums array and update tails. For each number num in nums we can do one of the following: If num is larger than all tails, then we extend the largest subsequence by adding num. If num is not larger than all tails, then we find the smallest tail that is >= num and replace with num. By doing this, we maintain the property that tails array is always sorted in increasing order.

Complexity:

• Time Complexity: O(n log n), where n is the length of the input array. This is because we iterate through the array once and perform a binary search for each element.
• Space Complexity: O(n), for the tails array.

import bisect

def lengthOfLIS_optimized(nums):
    tails = []
    for num in nums:
        i = bisect.bisect_left(tails, num)
        if i == len(tails):
            tails.append(num)
        else:
            tails[i] = num
    return len(tails)