Understanding Longest Increasing Subsequence in Java

Introduction & Problem Explanation

The Longest Increasing Subsequence (LIS) problem asks us to find the length of the longest subsequence of a given array of integers such that all elements of the subsequence are sorted in strictly increasing order.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, given the array [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101] or [2, 3, 7, 18], both having a length of 4. A standard dynamic programming approach solves this problem in O(n2) time. However, we can optimize this to O(n log n) time by combining dynamic programming with binary search (a technique related to Patience Sorting).

The Algorithmic Approach

DP with Binary Search (O(n log n) Time, O(n) Space)

We maintain an active list (or array) sub that represents the smallest tail of all increasing subsequences of various lengths found so far. As we iterate through each number num in the input array:

• We use binary search to find the insertion position of num in sub.
• If num is larger than all elements in sub, it means we can extend our longest increasing subsequence. We append num to the end of sub.
• Otherwise, we find the first element in sub that is greater than or equal to num and replace it with num. This swap optimizes future possibilities by reducing the tail value of that subsequence length, making it easier to append subsequent numbers.

At the end of the array traversal, the size of the sub list is the length of the LIS. Note: The elements in sub do not necessarily form the actual LIS, but its size is guaranteed to be correct.

Step-by-Step Execution Walkthrough

Let's trace the algorithm on the input array nums = [10, 9, 2, 5, 3]:

1. Step 1 (Initialization): Initialize an empty list: sub = [].
2. Step 2 (Element: 10):
   • Binary search for 10 in [] gives insertion index 0.
   • Since index 0 equals sub.size(), we append 10.
   • State: sub = [10]
3. Step 3 (Element: 9):
   • Binary search for 9 in [10] yields insertion index 0.
   • We replace the element at index 0 (10) with 9. (A sequence of length 1 ending in 9 is better than ending in 10).
   • State: sub = [9]
4. Step 4 (Element: 2):
   • Binary search for 2 in [9] yields insertion index 0.
   • We replace the element at index 0 (9) with 2.
   • State: sub = [2]
5. Step 5 (Element: 5):
   • Binary search for 5 in [2] yields insertion index 1.
   • Since index 1 equals sub.size(), we append 5.
   • State: sub = [2, 5]
6. Step 6 (Element: 3):
   • Binary search for 3 in [2, 5] yields insertion index 1.
   • We replace the element at index 1 (5) with 3. (A subsequence of length 2 ending in 3 is better than ending in 5).
   • State: sub = [2, 3]
7. Step 7 (Final Result): The list size is 2. We return 2.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• int i = Collections.binarySearch(sub, num);: Searches the list in O(log n) time. If the element is not found, it returns -(insertion_point + 1).
• if (i < 0) i = -(i + 1);: Converts a negative search result into the correct insertion point where the element should reside.
• sub.set(i, num);: The greedy replacement step. Lowering the tail element values increases our options for future numbers.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LongestIncreasingSubsequence {

    // DP with Binary Search: Time O(N log N), Space O(N)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        List<Integer> sub = new ArrayList<>();

        for (int num : nums) {
            // Find the index of the first element >= num
            int index = Collections.binarySearch(sub, num);
            
            // If not found, binarySearch returns -(insertionPoint + 1)
            if (index < 0) {
                index = -(index + 1);
            }

            // If num is larger than all elements in sub, append it
            if (index == sub.size()) {
                sub.add(num);
            } else {
                // Otherwise, replace the first element that is >= num
                sub.set(index, num);
            }
        }

        return sub.size();
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence solver = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};

        System.out.println("--- Longest Increasing Subsequence Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        int length = solver.lengthOfLIS(nums);
        System.out.println("Length of LIS: " + length); // Expected: 4 (e.g., [2, 3, 7, 18])
    }
}

Conclusion

Dynamic programming alone solves the LIS problem in quadratic time. By combining subproblem storage with binary search, we optimize search operations, achieving a highly efficient O(n log n) solution.