Longest Increasing Subsequence

Why it belongs on this sheet

This is a classic DP benchmark problem and a good way to practice subsequence-style transitions.

Pattern

Best LIS ending at each index

Approach

For each position, look at all earlier positions with smaller values and extend the best subsequence ending there. Track the largest value in the DP array.

Java solution

import java.util.Arrays;

class Solution {
  public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int best = 1;

    for (int i = 0; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      best = Math.max(best, dp[i]);
    }

    return best;
  }
}

Complexity

• Time: O(n^2)
• Space: O(n)

Interview note

The O(n log n) version is a strong follow-up, but the quadratic DP is often enough for a first pass.