DP 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm

This comprehensive study note explores the transition of the Longest Increasing Subsequence (LIS) problem from memoization to tabulation, space-optimized tabulation, and finally an algorithmic tabulation approach that enables us to reconstruct and print the actual subsequence elements.

1. Why Do We Need This? (From Memoization to Tabulation)

In previous sessions, we established a recursive solution with memoization to solve the LIS problem. While memoization prevents redundant overlapping subproblem computations, it still relies on recursion stack overhead.

• The Limitations of Memoization: Recursion requires stack space proportional to the depth of the recursive tree, which can lead to stack overflow errors for very large inputs ($N$).
• The Tabulation Goal: We want to eliminate recursion entirely by building solutions iteratively in a bottom-up table (DP array), improving system stability and opening doors for space optimization.

2. Core Mental Model: The Two Tabulation Perspectives

When tackling LIS via tabulation, there are two distinct mental frameworks:

1. The 2D Coordinate-Shift Tabulation: Directly mapping the recursive parameters (index, previous_index) into a 2D table with a coordinate shift (previous_index + 1).
2. The 1D Algorithmic Tabulation (dp[i]): Redefining the state so that dp[i] signifies the length of the longest increasing subsequence that ends specifically at index i.

3. Approach 1: 2D Tabulation & Space Optimization

Converting Recursion to a 2D Iterative Table

Following standard dynamic programming transformation rules:

1. Declare the DP Table: Create a 2D table of size (N + 1) \times (N + 2) to account for the coordinate shift where previous_index ranges from -1 to $N-1$.
2. Base Cases: When index == N, the length is 0. Since arrays default to zero in many languages, explicit base case initialization can often be omitted if bounds are set correctly.
3. Establish Loop Directions:
   • index runs backward from N - 1 down to 0.
   • previous_index runs from index - 1 down to -1.

Code Implementation: 2D Tabulation

int longestIncreasingSubsequence(int arr[], int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int index = n - 1; index >= 0; index--) {
        for (int prev_index = index - 1; prev_index >= -1; prev_index--) {
            int len = dp[index + 1][prev_index + 1]; // Not take
            if (prev_index == -1 || arr[index] > arr[prev_index]) {
                len = max(len, 1 + dp[index + 1][index + 1]); // Take
            }
            dp[index][prev_index + 1] = len;
        }
    }
    return dp[0][0 + 1];
}

Space Optimization Strategy

Notice that computing the row for index only ever requires values from the next row (index + 1). We can compress our space complexity from $O(N^2)$ down to $O(N)$ by maintaining just two rows: next and curr.

int spaceOptimizedLIS(vector<int>& arr) {
    int n = arr.size();
    vector<int> next(n + 1, 0), curr(n + 1, 0);

    for (int index = n - 1; index >= 0; index--) {
        for (int prev_index = index - 1; prev_index >= -1; prev_index--) {
            int len = next[prev_index + 1];
            if (prev_index == -1 || arr[index] > arr[prev_index]) {
                len = max(len, 1 + next[index + 1]);
            }
            curr[prev_index + 1] = len;
        }
        next = curr;
    }
    return next[0 + 1];
}

4. Approach 2: Alternative 1D Tabulation (dp[i] ends at i)

While 2D tabulation solves the length, it is difficult to trace back the actual sequence elements using just the 2D table. We introduce a cleaner 1D tabulation technique.

Definition of State

• dp[i] = Length of the longest increasing subsequence that ends at index i.
• Base Case: Every single element on its own is an increasing subsequence of length 1. Thus, initialize dp with all 1s.

Step-by-Step Execution on Sample Array

Let's trace the array: [5, 4, 11, 1, 16, 8]

• Maximum LIS Length: $\max(\text{dp}) = 3$ (found at index 4 where element is 16).

5. Complete Flow Walkthrough: 1D Tabulation Code

Here is the complete implementation of the 1D tabulation approach to compute the length of the LIS:

#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);
    int maxi = 1;

    for (int i = 0; i < n; i++) {
        for (int prev = 0; prev < i; prev++) {
            if (arr[prev] < arr[i]) {
                dp[i] = max(dp[i], 1 + dp[prev]);
            }
        }
        maxi = max(maxi, dp[i]);
    }
    return maxi;
}

6. Printing the Longest Increasing Subsequence (Backtracking)

To print the actual sequence, we need to remember where each element came from. We introduce a companion hash array (or parent array).

The Hash Array Strategy

• hash[i] stores the index of the previous element that contributed to the LIS ending at index i.
• Initialize every hash[i] = i (initially pointing to itself).
• Whenever dp[i] is updated via arr[prev] < arr[i], we record hash[i] = prev.
• We also keep track of the last_index where the maximum LIS length was finalized.

Traceback Algorithm

1. Start at last_index.
2. Push arr[last_index] into a temporary vector.
3. Jump to last_index = hash[last_index] until hash[last_index] == last_index.
4. Reverse the temporary vector to get the correct chronological order.

7. Complete Code: Printing LIS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printLIS(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1), hash(n);
    int maxi = 1;
    int last_index = 0;

    for (int i = 0; i < n; i++) {
        hash[i] = i; // Initialize hash to point to itself
        for (int prev = 0; prev < i; prev++) {
            if (arr[prev] < arr[i] && 1 + dp[prev] > dp[i]) {
                dp[i] = 1 + dp[prev];
                hash[i] = prev;
            }
        }
        if (dp[i] > maxi) {
            maxi = dp[i];
            last_index = i;
        }
    }

    // Backtrack to reconstruct the LIS
    vector<int> temp;
    temp.push_back(arr[last_index]);
    
    while (hash[last_index] != last_index) {
        last_index = hash[last_index];
        temp.push_back(arr[last_index]);
    }

    // Reverse to get the correct left-to-right order
    reverse(temp.begin(), temp.end());

    cout << "The LIS elements are: ";
    for (int it : temp) {
        cout << it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {5, 4, 11, 1, 16, 8};
    printLIS(arr);
    return 0;
}

8. Summary and Key Takeaways

• 2D Tabulation Translation: Follows strict rules of coordinate shifting (previous_index + 1) to eliminate recursion overhead.
• Space Optimization: Compresses the 2D DP table space complexity from $O(N^2)$ to $O(N)$ by keeping track of only the next and curr rows.
• 1D Algorithmic DP (dp[i]): Defines dp[i] as the LIS ending at index i, providing an intuitive foundation for sequence reconstruction.
• Complexity Analysis:
  • Time Complexity: $O(N^2)$ due to the nested loops checking all previous elements for each index.
  • Space Complexity: $O(N)$ for the 1D DP table, hash array, and traceback storage.
• Backtracking with Hash Array: By maintaining a parent pointer (hash array) alongside the DP table, we can easily trace back and print the exact subsequence elements.
• Next Frontier: While $O(N^2)$ tabulation is robust and enables printing, further optimization using Binary Search (std::lower_bound) can reduce the time complexity down to $O(N \log N)$.