Longest Increasing subsequence (binary search + DP)

XXX. Longest Increasing Subsequence

Dynamic Programming

Binary Search

Problem Statement:

Given an array of integers, find the length of the longest increasing subsequence (LIS).

A subsequence is derived from an array by deleting some or no elements without changing the order of the remaining elements.

Algorithm:

There are two main approaches to solving this problem:

1. Dynamic Programming (O(n²)):
   • Use a DP array where dp[i] represents the length of the LIS ending at index i.
   • For each pair of indices i and j where j < i, update dp[i] if nums[j] < nums[i].
   • Take the maximum value in the dp array as the result.
2. Binary Search with DP Array (O(n log n)):
   • Use a DP array to store the smallest ending values of increasing subsequences of various lengths.
   • For each element, find its position in the DP array using binary search.
   • Update the DP array to maintain the smallest possible ending value for increasing subsequences.

Complexity:

Dynamic Programming: O(n²) time and O(n) space.
Binary Search: O(n log n) time and O(n) space.

Explanation:

Binary Search Solution:

• Maintains a dp array where each index represents the smallest ending value of an increasing subsequence of that length.
• For each number in the input array:
• Perform a binary search in the dp array to find the index where the number can replace an existing value or extend the LIS.
• If the number is larger than all existing values, it extends the LIS.
• If the number is smaller, it replaces the first value in dp that is larger or equal, maintaining the smallest possible value.
• Efficient due to binary search, with O(n log n) time complexity.

Dynamic Programming Solution:

• Uses a dp array where dp[i] stores the length of the LIS ending at index i.
• For each element, checks all previous elements to see if it can extend any LIS ending before it.
• Updates the dp array and tracks the maximum LIS length.
• Simpler implementation but slower due to O(n²) complexity from nested loops.

Java Implementation:

// Optimal Binary Search Solution O(n log n)
public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0; // Handle empty input

    int len = 0; // Tracks length of the LIS
    int[] dp = new int[nums.length]; // DP array for LIS ending values

    for (int num : nums) {
        // Binary search for the insertion position in the DP array
        int i = Arrays.binarySearch(dp, 0, len, num);

        // Convert negative index to insertion point
        if (i < 0) i = -(i + 1);

        // Update or replace the value at the insertion point
        dp[i] = num;

        // If inserted at the end, increment the LIS length
        if (i == len) len++;
    }

    return len; // The length of the LIS
}

// Dynamic Programming Solution O(n²)
public int lengthOfLIS_DP(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1); // Each number is a subsequence of length 1
    int max = 1; // Tracks the maximum LIS length

    for (int i = 1; i < nums.length; i++) 
        for (int j = 0; j < i; j++) 
            if (nums[j] < nums[i]) { // Check if increasing subsequence
                dp[i] = Math.max(dp[j] + 1, dp[i]); // Update dp[i]
                max = Math.max(max, dp[i]); // Update maximum LIS length
            }

    return max; // Return the maximum LIS length
}