Given an unsorted array of integers, find the length of the longest increasing subsequence.

For example:

• Input: [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.

Another example:

• Input: [0, 1, 0, 3, 2, 3]
• Output: 4
• Explanation: One longest increasing subsequence is [0, 1, 2, 3].

Constraints:

• The array can contain duplicate numbers.
• The numbers are not necessarily positive. They can be negative or zero.
• Your solution should be as efficient as possible.

Could you describe your approach and implement the solution? Consider the time and space complexity of your solution.

In the first example, [10, 9, 2, 5, 3, 7, 101, 18], a longest increasing subsequence is [2, 3, 7, 18]. Note that subsequences are not required to be contiguous. Another longest increasing subsequence is [2, 5, 7, 101]. It is important to understand what "increasing" means. The numbers must be strictly increasing (e.g., 2, 3, 7 is increasing, but 2, 2, 7 is not). Another important point to note is that there may be multiple longest increasing subsequences, but your function should return the length of such a subsequence, not the subsequence itself.

Longest Increasing Subsequence

Problem Description

Given an unsorted array of integers, find the length of the longest increasing subsequence.

For example:

• Input: [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.

Another example:

• Input: [0, 1, 0, 3, 2, 3]
• Output: 4
• Explanation: One longest increasing subsequence is [0, 1, 2, 3].

Constraints:

• The array can contain duplicate numbers.
• The numbers are not necessarily positive. They can be negative or zero.
• Your solution should be as efficient as possible.

Approach

We can solve this problem using dynamic programming. We will maintain an array dp where dp[i] stores the length of the longest increasing subsequence ending at index i. We iterate through the input array and for each element, we iterate through all the preceding elements. If a preceding element is smaller than the current element, we update dp[i] with the maximum of its current value and dp[j] + 1, where j is the index of the preceding element. Finally, we return the maximum value in the dp array.

Another, more efficient approach uses binary search. We maintain an array tails where tails[i] is the smallest tail of all increasing subsequences with length i+1. For each number in the input array, we try to extend an existing subsequence by finding the smallest tail that is greater than or equal to the current number. If we find such a tail, we replace it with the current number because the current number gives us an increasing subsequence of the same length but with a smaller tail. If we don't find such a tail, it means the current number extends the longest increasing subsequence by 1. The length of the tails array is the length of the longest increasing subsequence.

Implementation

Dynamic Programming (O(n^2) solution)

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)

# Example usage
nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"Input: {nums1}, Output: {longest_increasing_subsequence_dp(nums1)}")

nums2 = [0, 1, 0, 3, 2, 3]
print(f"Input: {nums2}, Output: {longest_increasing_subsequence_dp(nums2)}")

Binary Search (O(n log n) solution)

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)

# Example usage
nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"Input: {nums1}, Output: {longest_increasing_subsequence_binary_search(nums1)}")

nums2 = [0, 1, 0, 3, 2, 3]
print(f"Input: {nums2}, Output: {longest_increasing_subsequence_binary_search(nums2)}")

Time Complexity

• Dynamic Programming: The time complexity is O(n^2) because of the nested loops.
• Binary Search: The time complexity is O(n log n) because we iterate through the array once (O(n)) and perform a binary search for each element (O(log n)).

Space Complexity

• Dynamic Programming: The space complexity is O(n) because we use an array dp of size n to store the lengths of the longest increasing subsequences ending at each index.
• Binary Search: The space complexity is O(n) in the worst case. The tails array can grow up to the size of the input array if the input array is strictly increasing.

Edge Cases

• Empty Array: If the input array is empty, the length of the longest increasing subsequence is 0. The code handles this case correctly.
• Array with Duplicate Numbers: The array can contain duplicate numbers. The code handles this case correctly because we are looking for a strictly increasing subsequence. Duplicate numbers will not be included in the subsequence.
• Array with Negative Numbers: The array can contain negative numbers. The code handles this case correctly.
• Array in Descending Order: If the array is in descending order, the length of the longest increasing subsequence is 1. The code handles this case correctly.
• Array with All Same Numbers: If the array contains all the same numbers, the length of the longest increasing subsequence is 1. The code handles this case correctly.