Longest Increasing Subsequence

Master this topic with zero to advance depth.

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

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

Visual Representation

nums = [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 18] or [2, 3, 7, 101]
Length: 4

DP Strategy:
dp[i] = length of LIS ending at index i
dp[i] = 1 + max(dp[j]) for all j < i AND nums[j] < nums[i]

Medium

Examples

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Approach 1

Level I: Dynamic Programming (O(N^2))

Intuition

For each element nums[i], we look back at all previous elements nums[j]. If nums[i] > nums[j], then nums[i] can extend the increasing subsequence ending at j.

Thought Process

Initialize dp array where dp[i] = 1 (minimum length is always 1).
For each i from 1 to n-1:
- For each j from 0 to i-1:
  - If nums[i] > nums[j]: dp[i] = max(dp[i], 1 + dp[j]).
Return the maximum value in dp.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [10, 9, 2, 5]

i	nums[i]	j loop	dp table	Max reached
0	10	-	[1, 1, 1, 1]	1
1	9	j=0 (9<10)	[1, 1, 1, 1]	1
2	2	j=0, 1 (2<9,10)	[1, 1, 1, 1]	1
3	5	j=2 (5>2)	[1, 1, 1, 2]	2

java

import java.util.Arrays;

public class Main {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxLIS = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxLIS = Math.max(maxLIS, dp[i]);
        }
        return maxLIS;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

Approach 2

Level II: Memoization (Top-Down DP)

Intuition

The brute force recursive approach recalculates the same subproblems repeatedly. We can cache results using a memo array so that each dp[i] is computed only once.

Thought Process

Initialize memo array with -1.
For solve(i), if memo[i] != -1, return it.
Otherwise, compute dp[i] = 1 + max(solve(j)) for all j < i where nums[j] < nums[i].
memo[i] = dp[i].

Visual

Recursion Tree (with memoization):
solve(7): max over j < 7 where nums[j] < 18
  - solve(6): 2 (cached at step 1)
  - solve(5): 3 (cached at step 2)
  - ... (all others are cached)

⏱ O(N^2)💾 O(N) for cache + recursion stack

Detailed Dry Run

nums = [10, 9, 2, 5]

call	i	j checks	result
1	0	-	1
2	1	j=0 (9<10)=No	1
3	2	j=0,j=1 (2<9,10)=No	1
4	3	j=2 (5>2)	2 (cached!)

java

import java.util.Arrays;

public class Main {
    static int[] memo;
    public static int solve(int[] nums, int i) {
        if (memo[i] != -1) return memo[i];
        memo[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                memo[i] = Math.max(memo[i], 1 + solve(nums, j));
            }
        }
        return memo[i];
    }

    public static int lengthOfLIS(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        int max = 0;
        for (int i = 0; i < nums.length; i++) max = Math.max(max, solve(nums, i));
        return max;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

⚠️ Common Pitfalls & Tips

When computing max across all solve(i) calls, don't forget that lru_cache in Python caches the function but the outer max call still needs to iterate all indices.

Approach 3

Level III: Binary Search (O(N log N))

Intuition

This is often called Patience Sorting. We maintain a list tails where tails[i] is the smallest tail of all increasing subsequences of length i+1.

Logic Steps

For each x in nums:
- If x is larger than the largest tail, append it.
- Otherwise, find the smallest tail \ge x using binary search and replace it with x.
The length of tails is the LIS length.

⏱ O(N log N)💾 O(N)

Detailed Dry Run

nums = [10, 9, 2, 5]

x	tails	Action	Reason
10	[10]	Append	List empty
9	[9]	Replace 10	9 is smaller tail for len 1
2	[2]	Replace 9	2 is smaller tail for len 1
5	[2, 5]	Append	5 > 2, starts len 2

java

import java.util.*;

public class Main {
    public static int lengthOfLIS(int[] nums) {
        ArrayList<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int i = Collections.binarySearch(tails, x);
            if (i < 0) i = -(i + 1);
            if (i == tails.size()) tails.add(x);
            else tails.set(i, x);
        }
        return tails.size();
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18})); // 4
    }
}

⚠️ Common Pitfalls & Tips

The Binary Search approach only gives the length of the LIS, correctly. The tails array itself may NOT represent a valid LIS (e.g., it might be mixed from different subsequences), but its size will always be correct.

← Previous QuestionKoko Eating Bananas

Next Question →Unique Paths

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.