Dynamic Programming: Longest Increasing Subsequence (LIS) | Memoization

This comprehensive pedagogical note covers the foundational concepts, recursive problem formulation, memoization optimization, and production pitfalls of the Longest Increasing Subsequence (LIS) pattern.

1. Why Do We Need a New DP Pattern?

• Status Quo: Previous Dynamic Programming chapters (DP 13 to DP 22) focused on subarrays, grid paths, and strings.
• The Subsequence Definition: A subsequence is formed by picking elements from an array while preserving their relative order. Elements can be contiguous or non-contiguous, but swapping elements destroys the subsequence property.
• The "Increasing" Constraint: Unlike general subsequences, an Increasing Subsequence requires strict ordering where every picked element is strictly greater than the one before it. Duplicate or decreasing values are forbidden.
• Problem Statement: Given an array of $n$ numbers, find the length of the longest possible subsequence whose elements are strictly increasing.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Imagine walking up a flight of stairs where each step must be strictly higher than the previous step you stood on. You cannot step backward or stay at the same elevation. When deciding whether to step onto a new platform, you must remember the height of the last platform you stepped on to ensure it is taller.

In LIS, you cannot make decisions in a vacuum. Your ability to include the current element depends entirely on what you picked previously.

3. Naive Brute Force Approach

The most intuitive brute force approach is to generate every possible subsequence, check if each one is strictly increasing, and track the maximum length found.

• Time Complexity: $\mathcal{O}(2^n)$ because an array of length $n$ has $2^n$ possible subsequences.
• Verdict: Exponential time complexity leads to immediate Time Limit Exceeded (TLE) errors for moderate constraints.

4. Recursive Formulation: The Take / Not-Take Pattern

Following the standard pattern for subsequence problems, we evaluate choices at every index: either take the element or not take it.

Function Definition

We define our recursive function as f(index, previous_index):

• index: The current element we are evaluating.
• previous_index: The index of the last element we successfully included in our increasing subsequence (stored as -1 if no element has been picked yet).

Recurrence Relations

1. Not-Take Case: Skip the current element.
   • Move to index + 1.
   • previous_index remains unchanged.
   • Length does not increase.
2. Take Case: Include the current element. Condition: We can only take the current element if previous_index == -1 or if array[index] > array[previous_index].
   • Move to index + 1.
   • Update previous_index to the current index.
   • Add 1 to the length.

5. Step-by-Step Recursive Code

Here is the raw recursive implementation demonstrating the explore-all-possibilities paradigm:

int f(int index, int prev_index, vector<int>& nums, int n) {
    // Base Case: Out of bounds
    if (index == n) return 0;
    
    // Option 1: Not take current element
    int notTake = 0 + f(index + 1, prev_index, nums, n);
    
    // Option 2: Take current element (if valid)
    int take = 0;
    if (prev_index == -1 || nums[index] > nums[prev_index]) {
        // Current index becomes the new previous index for the next recursive call
        take = 1 + f(index + 1, index, nums, n);
    }
    
    return max(notTake, take);
}

6. Overlapping Subproblems & Memoization Strategy

If you draw the complete recursion tree, you will notice identical subproblems (index and prev_index states) being computed repeatedly. We can cache these results using a 2D DP table.

The Coordinate Shift Challenge

• index ranges from 0 to n - 1.
• prev_index ranges from -1 to n - 1.

Because standard arrays cannot use negative indices like -1, we perform a coordinate shift by shifting all prev_index values by $+1$:

• -1 maps to index 0
• 0 maps to index 1
• 1 maps to index 2
• ...
• n - 1 maps to index n

Therefore, our DP table dimensions need to be [n][n + 1].

7. Complete Memoized Solution (C++)

Below is the optimized memoized solution integrating the coordinate shift:

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

class Solution {
private:
    int getLIS(int index, int prev_index, vector<int>& nums, int n, vector<vector<int>>& dp) {
        // Base case
        if (index == n) return 0;
        
        // Check memoized table (with coordinate shift for prev_index)
        if (dp[index][prev_index + 1] != -1) {
            return dp[index][prev_index + 1];
        }
        
        // Not take
        int notTake = getLIS(index + 1, prev_index, nums, n, dp);
        
        // Take
        int take = 0;
        if (prev_index == -1 || nums[index] > nums[prev_index]) {
            take = 1 + getLIS(index + 1, index, nums, n, dp);
        }
        
        // Store and return result
        return dp[index][prev_index + 1] = max(notTake, take);
    }

public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // DP table dimensions: n rows (index) x (n + 1) columns (prev_index shifted)
        vector<vector<int>> dp(n, vector<int>(n + 1, -1));
        return getLIS(0, -1, nums, n, dp);
    }
};

8. Real-World Practical Pitfalls & Constraints Reality Check

• Memory Limit / Runtime Errors: If problem constraints specify $n = 10^5$, creating a 2D DP table of size $n \times n$ ($10^5 \times 10^5 = 10^{10}$ operations/memory cells) will immediately trigger a Memory Limit Exceeded (MLE) or Runtime Error.
• When Memoization Falls Short: Memoization with $\mathcal{O}(n^2)$ space complexity is ideal for $n \le 5000$. For larger constraints ($n = 10^5$), we must transition to advanced Tabulation with Binary Search ($\mathcal{O}(n \log n)$).

9. Summary and Key Takeaways

• Subsequence Definition: Preserves relative element order without requiring contiguous blocks.
• Strictly Increasing Rule: Equal or smaller elements cannot be part of an increasing subsequence.
• Recursive State Representation: Defined by (index, previous_index).
• Core Choices: At every step, evaluate notTake (skip index) and take (include if greater than previous).
• Base Case: Reaching index n returns length 0.
• Coordinate Shift: Essential in memoization to handle prev_index = -1 inside 0-indexed arrays by shifting columns by +1.
• Complexity Trade-off:
  • Recursion: Time $\mathcal{O}(2^n)$, Space $\mathcal{O}(n)$
  • Memoization: Time $\mathcal{O}(n^2)$, Space $\mathcal{O}(n^2)$