Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem: Find the length of the longest subsequence where elements are in strictly increasing order.

Definition

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

DP Approach: O(n^2)

// dp[i] = length of LIS ending at index i
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // Each element is LIS of length 1
    
    int maxLength = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    
    return maxLength;
}

Trace Example

nums = [10, 9, 2, 5, 3, 7, 101, 18]

dp[0] = 1  (10)
dp[1] = 1  (9, no previous smaller)
dp[2] = 1  (2, no previous smaller)
dp[3] = 2  (2 < 5, extend from dp[2])
dp[4] = 2  (2 < 3, extend from dp[2])
dp[5] = 3  (2 < 3 < 7, extend from dp[4])
dp[6] = 4  (3 < 7 < 101, extend from dp[5])
dp[7] = 4  (3 < 7 < 18, extend from dp[5])

Answer: 4 (subsequence: [2, 3, 7, 101] or [2, 3, 7, 18])

Reconstructing the LIS

public List<Integer> reconstructLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int[] parent = new int[n];  // Track previous index in LIS
    Arrays.fill(dp, 1);
    Arrays.fill(parent, -1);
    
    int maxLength = 1;
    int maxIndex = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;  // Record predecessor
            }
        }
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            maxIndex = i;
        }
    }
    
    // Reconstruct path
    List<Integer> lis = new ArrayList<>();
    int curr = maxIndex;
    while (curr != -1) {
        lis.add(0, nums[curr]);
        curr = parent[curr];
    }
    
    return lis;
}

Time and Space Complexity

• Time: O(n^2) - two nested loops
• Space: O(n) - dp and parent arrays

When O(n^2) is Acceptable

• n <= 1000
• Need to reconstruct the actual LIS
• Need to find all LIS of maximum length

Patience Sorting Approach

Maintain an array tails where tails[i] is the smallest tail element for increasing subsequences of length i+1.

// O(n log n) time, O(n) space
public int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    
    for (int num : nums) {
        // Find position where num should be placed
        int pos = Collections.binarySearch(tails, num);
        
        if (pos < 0) {
            pos = -(pos + 1);  // Insertion point
        }
        
        if (pos == tails.size()) {
            tails.add(num);  // Extend longest subsequence
        } else {
            tails.set(pos, num);  // Replace to keep smallest tail
        }
    }
    
    return tails.size();
}

Why It Works

nums = [10, 9, 2, 5, 3, 7, 101, 18]

num=10:  tails = [10]
num=9:   tails = [9]       (replace 10)
num=2:   tails = [2]       (replace 9)
num=5:   tails = [2, 5]    (extend)
num=3:   tails = [2, 3]    (replace 5)
num=7:   tails = [2, 3, 7] (extend)
num=101: tails = [2, 3, 7, 101] (extend)
num=18:  tails = [2, 3, 7, 18]  (replace 101)

Answer: tails.size() = 4

Important Note

The tails array is NOT the LIS itself! It only gives the length. To reconstruct, you need additional tracking.

Reconstructing LIS with O(n log n)

public List<Integer> reconstructLIS(int[] nums) {
    int n = nums.length;
    List<Integer> tails = new ArrayList<>();
    int[] tailIndices = new int[n];  // Index in tails array
    int[] parent = new int[n];       // Previous index in LIS
    Arrays.fill(parent, -1);
    
    for (int i = 0; i < n; i++) {
        int pos = Collections.binarySearch(tails, nums[i]);
        if (pos < 0) pos = -(pos + 1);
        
        if (pos == tails.size()) {
            tails.add(nums[i]);
        } else {
            tails.set(pos, nums[i]);
        }
        
        tailIndices[i] = pos;
        if (pos > 0) {
            // Find the last element with tailIndices = pos - 1
            for (int j = i - 1; j >= 0; j--) {
                if (tailIndices[j] == pos - 1) {
                    parent[i] = j;
                    break;
                }
            }
        }
    }
    
    // Reconstruct
    int lisLen = tails.size();
    List<Integer> lis = new ArrayList<>();
    int curr = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (tailIndices[i] == lisLen - 1) {
            curr = i;
            break;
        }
    }
    
    while (curr != -1) {
        lis.add(0, nums[curr]);
        curr = parent[curr];
    }
    
    return lis;
}

LIS Variants

Longest Decreasing Subsequence:

// Negate all numbers, then find LIS
public int LDS(int[] nums) {
    int[] negated = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        negated[i] = -nums[i];
    }
    return lengthOfLIS(negated);
}

Longest Bitonic Subsequence:

// Find LIS from left and LDS from right
public int longestBitonic(int[] nums) {
    int n = nums.length;
    int[] lis = new int[n];
    int[] lds = new int[n];
    
    // LIS from left
    for (int i = 0; i < n; i++) {
        lis[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                lis[i] = Math.max(lis[i], lis[j] + 1);
            }
        }
    }
    
    // LDS from right
    for (int i = n - 1; i >= 0; i--) {
        lds[i] = 1;
        for (int j = n - 1; j > i; j--) {
            if (nums[j] < nums[i]) {
                lds[i] = Math.max(lds[i], lds[j] + 1);
            }
        }
    }
    
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        maxLen = Math.max(maxLen, lis[i] + lds[i] - 1);
    }
    
    return maxLen;
}

Complexity Comparison

Approach	Time	Space	Reconstruct?
DP O(n^2)	O(n^2)	O(n)	Yes
Binary Search	O(n log n)	O(n)	Yes (with extra work)