Longest Increasing Subsequence

Given an integer array nums, return *the length of the longest *strictly increasing subsequence. For example:

• nums = [10,9,2,5,3,7,101,18] Output: 4 because the longest increasing subsequence is [2,3,7,101]
• nums = [0,1,0,3,2,3] Output: 4
• nums = [7,7,7,7,7,7,7] Output: 1

What approach would you take to solve this problem, and what is the time and space complexity of your solution? Consider the edge cases, such as an empty array or an array with all the same elements.

# Longest Increasing Subsequence

## Problem Description

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

For example:

*   `nums = [10, 9, 2, 5, 3, 7, 101, 18]`
    The longest increasing subsequence is `[2, 3, 7, 101]`, so the length is 4.
*   `nums = [0, 1, 0, 3, 2, 3]`
    The longest increasing subsequence is `[0, 1, 2, 3]`, so the length is 4.
*   `nums = [7, 7, 7, 7, 7, 7, 7]`
    The longest increasing subsequence is `[7]`, so the length is 1.

## Brute Force Solution

A brute force solution 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 strictly increasing subsequence found so far. This approach has exponential time complexity because there are 2^n possible subsequences of an array of size n.

```python
def longest_increasing_subsequence_brute_force(nums):
    def generate_subsequences(nums):
        if not nums:
            return [[]]
        
        first = nums[0]
        rest = nums[1:]
        
        subsequences_without_first = generate_subsequences(rest)
        subsequences_with_first = [[first] + sub for sub in subsequences_without_first]
        
        return subsequences_without_first + subsequences_with_first

    def is_strictly_increasing(subsequence):
        if len(subsequence) <= 1:
            return True
        for i in range(len(subsequence) - 1):
            if subsequence[i] >= subsequence[i+1]:
                return False
        return True

    max_len = 0
    for subsequence in generate_subsequences(nums):
        if is_strictly_increasing(subsequence):
            max_len = max(max_len, len(subsequence))
    return max_len

Optimal Solution (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. The base case is dp[0] = 1. For each i > 0, we iterate through all j < i. If nums[i] > nums[j], then we can extend the longest increasing subsequence ending at j by adding nums[i] to it. Thus, dp[i] = max(dp[i], dp[j] + 1). The final answer is the maximum value in the dp array.

def longest_increasing_subsequence_dp(nums):
    n = len(nums)
    if n == 0:
        return 0

    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)

Optimal Solution (Binary Search)

We can further optimize this solution using binary search. We maintain a tails array, where tails[i] is the smallest tail of all increasing subsequences of length i+1. For each number in nums, we try to extend the longest increasing subsequence seen so far. If the current number is greater than all tails, it extends the longest increasing subsequence by 1. If it is not, we can use binary search to find the smallest tail that is greater than or equal to the current number and replace that tail with the current number. The length of the tails array is the length of the longest increasing subsequence.

import bisect

def longest_increasing_subsequence_binary_search(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)

Big(O) Run-time Analysis (Dynamic Programming)

The dynamic programming solution has a time complexity of O(n^2), where n is the length of the input array. This is because we have two nested loops, where the outer loop iterates from 1 to n-1, and the inner loop iterates from 0 to i-1.

Big(O) Run-time Analysis (Binary Search)

The binary search solution has a time complexity of O(n log n), where n is the length of the input array. This is because we iterate through the array once, and for each element, we perform a binary search, which takes O(log n) time.

Big(O) Space Usage Analysis (Dynamic Programming)

The dynamic programming solution has a space complexity of O(n), where n is the length of the input array. This is because we use an array dp of size n to store the lengths of the longest increasing subsequences ending at each index.

Big(O) Space Usage Analysis (Binary Search)

The binary search solution has a space complexity of O(n) in the worst case, where n is the length of the input array. This is because in the worst case, the tails array can store all the elements of the input array if the input array is strictly increasing.

Edge Cases

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