Dynamic Programming for Longest Increasing Subsequence: From O(N²) to O(N log N) Algorithm Evolution

Problem Definition and Basic Concepts

The Longest Increasing Subsequence (LIS) problem requires finding a subsequence within a given integer sequence such that the elements are strictly increasing and its length is maximized. For example, in the sequence [2, 6, 3, 4, 1, 2, 9, 5, 8], an LIS is [2, 3, 4, 5, 8] with length 5. Dynamic programming is a classic method for such optimization problems, avoiding redundant computations by breaking the problem into overlapping subproblems.

O(N²) Dynamic Programming Solution

Let the array arr have length N with indices from 0 to N-1. Define state dp[i] as the length of the longest increasing subsequence ending at element i. Initially, each element forms a subsequence of length 1, so dp[i] = 1. The state transition relies on the observation: for each i, iterate over all j < i, and if arr[j] < arr[i], then arr[i] can be appended to the subsequence ending at arr[j], updating dp[i] = max(dp[i], dp[j] + 1). Finally, the LIS length is max(dp[0...N-1]).

int[] dp = new int[N];
int[] prev = new int[N]; // for reconstruction
int maxLength = 1, bestEnd = 0;

for (int i = 0; i < N; i++) {
    dp[i] = 1;
    prev[i] = -1; // initialize predecessor pointer
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
            prev[i] = j;
        }
    }
    if (dp[i] > maxLength) {
        maxLength = dp[i];
        bestEnd = i;
    }
}

To reconstruct the LIS, start from bestEnd and backtrack using the prev array until -1 is encountered. For the example sequence, dp is [1, 2, 2, 3, 1, 2, 4, 4, 5], with max length 5 at index 8, yielding the subsequence [2, 3, 4, 5, 8] via prev. This method has time complexity O(N²) and space complexity O(N), suitable for small datasets or educational purposes.

O(N log N) Efficient Algorithm

To optimize to O(N log N), introduce an array S where S[pos] stores the smallest possible ending element of an increasing subsequence of length pos+1. The algorithm iterates through each element X of the input sequence:

1. If X is greater than the last element of S, append X to S, indicating a longer subsequence has been found.
2. Otherwise, perform a binary search in S for the first element greater than or equal to X, and replace it with X. This maintains the increasing order of S and provides smaller ending values for potential extensions.

Since S remains sorted, each binary search takes O(log N), resulting in overall O(N log N) complexity. The following code illustrates this process:

List<Integer> S = new ArrayList<>();
List<Integer> parent = new ArrayList<>(); // store predecessor indices

for (int i = 0; i < N; i++) {
    int X = arr[i];
    if (S.isEmpty() || X > S.get(S.size() - 1)) {
        S.add(X);
        parent.add(i); // predecessor is the previous last index
    } else {
        int idx = Collections.binarySearch(S, X);
        if (idx < 0) idx = -idx - 1; // adjust for binary search
        S.set(idx, X);
        parent.set(idx, i); // update predecessor
    }
}

For the sequence [2, 6, 3, 4, 1, 2, 9, 5, 8], S evolves as: [] → [2] → [2,6] → [2,3] → [2,3,4] → [1,3,4] → [1,2,4] → [1,2,4,9] → [1,2,4,5] → [1,2,4,5,8]. The final length of S, 5, is the LIS length. Reconstruction uses the parent array to backtrack from the last element, obtaining the actual subsequence.

Algorithm Comparison and Applications

The O(N²) method is intuitive and ideal for beginners to grasp dynamic programming fundamentals, but inefficient for large-scale data (e.g., N > 10⁴). The O(N log N) algorithm significantly boosts performance via binary search, making it the preferred choice in modern applications, such as analyzing DNA sequences in bioinformatics or monitoring trends in data streams. Space complexity is O(N) for both, though the latter may require additional structures like parent for reconstruction.

In practice, edge cases like empty inputs or strictly decreasing sequences must be handled. The algorithms can be extended for non-strict increasing sequences (allowing equals) by adjusting comparison logic; for example, change arr[j] < arr[i] to arr[j] <= arr[i].

In summary, the LIS problem illustrates a complete path from basic to optimized dynamic programming, highlighting trade-offs in algorithm design. Mastering these approaches not only solves specific problems but also deepens understanding of core computer science concepts like state design and binary search.