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

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

# Longest Increasing Subsequence

## Problem Description

Given an integer array `nums`, the goal is to find the length of the longest strictly increasing subsequence.

For example:

- Input: `nums = [10, 9, 2, 5, 3, 7, 101, 18]`
  Output: `4` (The longest increasing subsequence is `[2, 3, 7, 101]`)

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

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

## Brute Force Solution

A brute-force approach would involve generating all possible subsequences and checking if each one is strictly increasing. Then, we select the longest of these increasing subsequences.

```python
def longest_increasing_subsequence_brute_force(nums):
    def generate_subsequences(index, current_subsequence):
        if index == len(nums):
            if len(current_subsequence) > 0:
                yield current_subsequence
            else:
                yield []
            return

        yield from generate_subsequences(index + 1, current_subsequence)
        yield from generate_subsequences(index + 1, current_subsequence + [nums[index]])

    max_len = 0
    for subsequence in generate_subsequences(0, []):
        is_increasing = True
        for i in range(1, len(subsequence)):
            if subsequence[i] <= subsequence[i-1]:
                is_increasing = False
                break
        if is_increasing:
            max_len = max(max_len, len(subsequence))

    return max_len

This approach is highly inefficient due to the exponential number of subsequences that need to be checked.

Optimal Solution (Dynamic Programming)

We can use dynamic programming to solve this problem more efficiently. The idea is to maintain an array dp where dp[i] represents the length of the longest increasing subsequence ending at index i.

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

    n = len(nums)
    dp = [1] * n  # Initialize dp array with 1 (each element is a subsequence of length 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)  # Extend the subsequence ending at j if possible

    return max(dp)

def longest_increasing_subsequence_nlogn(nums):
    tails = []
    for num in nums:
        if not tails or num > tails[-1]:
            tails.append(num)
        else:
            # Binary search to find the smallest tail >= num
            l, r = 0, len(tails) - 1
            while l <= r:
                mid = (l + r) // 2
                if tails[mid] < num:
                    l = mid + 1
                else:
                    r = mid - 1
            tails[l] = num
    return len(tails)

Example with Dynamic Programming

Let's trace the example nums = [10, 9, 2, 5, 3, 7, 101, 18] using dynamic programming.

1. Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1]
2. i = 1, nums[1] = 9
   • j = 0, nums[0] = 10. 9 > 10 is false. dp[1] remains 1.
3. i = 2, nums[2] = 2
   • j = 0, nums[0] = 10. 2 > 10 is false.
   • j = 1, nums[1] = 9. 2 > 9 is false. dp[2] remains 1.
4. i = 3, nums[3] = 5
   • j = 0, nums[0] = 10. 5 > 10 is false.
   • j = 1, nums[1] = 9. 5 > 9 is false.
   • j = 2, nums[2] = 2. 5 > 2 is true. dp[3] = max(1, 1 + 1) = 2.
5. Continue this process. The final dp array will be [1, 1, 1, 2, 2, 3, 4, 4].
6. The maximum value in dp is 4, which is the length of the longest increasing subsequence.

Time Complexity Analysis

Dynamic Programming

The time complexity of the dynamic programming solution is O(n^2) because of the nested loops, where n is the length of the input array.

Optimal Solution with Binary Search

The time complexity of the optimal solution using binary search is O(n log n) because we iterate through the array once (O(n)), and for each element, we perform a binary search (O(log n)).

Space Complexity Analysis

Dynamic Programming

The space complexity of the dynamic programming solution is O(n) because we use an array dp of length n to store the lengths of the longest increasing subsequences.

Optimal Solution with Binary Search

The space complexity of the optimal solution using binary search is O(n) in the worst case because the tails array can potentially store all the elements of the input array if the input array is strictly increasing.

Edge Cases

1. Empty Input Array: If the input array is empty, the length of the longest increasing subsequence is 0.
2. Array with Identical Elements: If the array contains only identical elements, the length of the longest increasing subsequence is 1.
3. Array in Descending Order: If the array is in strictly descending order, the length of the longest increasing subsequence is 1.

These edge cases are handled correctly by the provided solutions.