Longest Increasing 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
• -10^4 <= nums[i] <= 10^4

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

## Longest Increasing Subsequence

This problem asks us to find the length of the longest strictly increasing subsequence within a given integer array. Let's explore different approaches to solve this problem.

### 1. Brute Force Approach

The most straightforward approach is to generate all possible subsequences of the input array and then check each subsequence to see if it's strictly increasing. We keep track of the longest increasing subsequence found so far.

**Code (Python):**

```python
def longest_increasing_subsequence_brute_force(nums):
    def is_increasing(subsequence):
        for i in range(len(subsequence) - 1):
            if subsequence[i] >= subsequence[i+1]:
                return False
        return True

    def generate_subsequences(index, current_subsequence):
        if index == len(nums):
            if is_increasing(current_subsequence):
                return len(current_subsequence)
            else:
                return 0

        # Option 1: Include the current element
        include = generate_subsequences(index + 1, current_subsequence + [nums[index]])
        
        # Option 2: Exclude the current element
        exclude = generate_subsequences(index + 1, current_subsequence)
        
        return max(include, exclude)

    return generate_subsequences(0, [])

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

Explanation:

• The is_increasing function checks if a given subsequence is strictly increasing.
• The generate_subsequences function recursively generates all subsequences.
• For each element in the input array, we have two choices: either include it in the current subsequence or exclude it.
• If a subsequence is strictly increasing, we update the maximum length found so far.

Big O Analysis:

• Time Complexity: O(2ⁿ * n), where n is the length of the input array. We generate 2ⁿ subsequences, and for each subsequence, we need to check if it's increasing, which takes O(n) time.
• Space Complexity: O(n) due to the recursion depth.

2. Dynamic Programming Approach

A more efficient approach is to use dynamic programming. We can define dp[i] as the length of the longest increasing subsequence ending at index i. The algorithm iterates through the array and builds the dp array by considering all possible preceding elements.

Code (Python):

def longest_increasing_subsequence_dp(nums):
    n = len(nums)
    dp = [1] * n  # Initialize dp array with 1 (each element is an increasing subsequence of length 1)

    for i in range(1, n):
        for j in range(0, i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

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

Explanation:

• dp[i] stores the length of the longest increasing subsequence ending at nums[i].
• We iterate through the array from left to right.
• For each element nums[i], we iterate through all preceding elements nums[j] (where j < i).
• If nums[i] > nums[j], it means we can extend the longest increasing subsequence ending at nums[j] by appending nums[i] to it.
• We update dp[i] to be the maximum of its current value and dp[j] + 1.
• Finally, the maximum value in the dp array is the length of the longest increasing subsequence.

Big O Analysis:

• Time Complexity: O(n²), where n is the length of the input array. The nested loops dominate the runtime.
• Space Complexity: O(n) for the dp array.

3. Optimized Approach with Binary Search

We can further optimize the solution using binary search. Instead of storing the lengths of the increasing subsequences, we store the smallest end element for each possible subsequence length. This allows us to use binary search to find the appropriate position to update.

Code (Python):

import bisect

def longest_increasing_subsequence_optimized(nums):
    tails = []  # tails[i] is the smallest tail of all increasing subsequences with length i+1

    for num in nums:
        # If num is greater than all tails, extend the longest increasing subsequence by 1
        if not tails or num > tails[-1]:
            tails.append(num)
        else:
            # Find the smallest tail that is >= num and replace it with num
            # This maintains the invariant that tails is always sorted
            index = bisect.bisect_left(tails, num)
            tails[index] = num

    return len(tails)

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

Explanation:

• tails[i] stores the smallest tail of all increasing subsequences of length i+1.
• We iterate through the input array nums.
• If the current number num is greater than the last element in tails, it means we can extend the longest increasing subsequence by 1. We append num to tails.
• Otherwise, we use binary search (bisect.bisect_left) to find the smallest element in tails that is greater than or equal to num. We replace that element with num. This maintains the invariant that tails is always sorted in increasing order.
• The length of the tails array is the length of the longest increasing subsequence.

Big O Analysis:

• Time Complexity: O(n log n), where n is the length of the input array. We iterate through the array once, and for each element, we perform a binary search, which takes O(log n) time.
• Space Complexity: O(n) for the tails array. In the worst case, the tails array can store all elements of the input array if the input array is strictly increasing.

Edge Cases

1. Empty Input: If the input array is empty, the longest increasing subsequence has length 0. The code handles this case correctly because the loops won't execute.
2. All Elements are the Same: If all elements in the input array are the same, the longest increasing subsequence has length 1. This is handled correctly by the dynamic programming approach, where each dp[i] is initialized to 1, and no updates occur since no element is greater than any preceding element. The optimized approach will also return 1 since the tails array will only contain one element.
3. Decreasing Array: If the array is strictly decreasing (e.g., [5, 4, 3, 2, 1]), the longest increasing subsequence has length 1. Similar to the case with all same elements, the code handles this correctly.
4. Large Input Array: The dynamic programming approach may become slow for very large input arrays due to its O(n²) time complexity. The optimized approach with binary search is much more efficient in such cases.

These approaches effectively solve the Longest Increasing Subsequence problem with varying time and space complexities.