Longest Increasing Subsequence

Medium20–25 min

Topics

Dynamic ProgrammingArrayBinary Search

Companies

AmazonMicrosoftAdobe

Given an array of integers, find the length of its longest strictly increasing subsequence — a run of elements, not necessarily touching in the original array, that keeps its relative left-to-right order while strictly climbing in value at every step. Every index can either join the subsequence being built or sit out, and whether it's allowed to join depends only on which number was chosen right before it. That makes "the best subsequence achievable from here onward, given the last number picked" a self-contained sub-problem: once it's known for every index and every possible predecessor, the overall answer just picks the largest one reachable from the very start. Since a number can only ever extend a run that ended on something smaller, sweeping through the array once and, for each position, checking every earlier position that could have preceded it is enough to fill in every sub-problem's answer using only ones already finished.

Test Case 1:

Input:nums = [11, 4, 7, 2, 9, 6, 14, 3]

Output:4

Explanation:One longest increasing run is 4, 7, 9, 14 — length 4. 2, 6, 14 is shorter; either valid answer only needs the length.

Test Case 2:

Input:nums = [2, 5, 2, 8, 6, 9]

Output:4

Explanation:2, 5, 8, 9 (the first 2, then 5, then later 8 and 9) is a length-4 increasing subsequence, and nothing longer exists.

Test Case 3:

Input:nums = [5, 5, 5, 5, 5, 5, 5]

Output:1

Explanation:Every element is equal, so no two elements are strictly increasing — the best any single element can do is a subsequence of length 1.

Constraints

◆1 ≤ nums.length ≤ 12
◆-1000 ≤ nums[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

At every index there are exactly two choices: leave the current number out of the subsequence, or fold it in as the new last element — but only when it's still increasing, meaning it's larger than whatever number was picked most recently. Tracking that "most recently picked" number as a second parameter alongside the current index turns the whole problem into a tree of skip/take decisions: try leaving the number out, try taking it (when allowed), and keep whichever path reaches the end of the array having picked more numbers. Nothing about a decision at one index is remembered when a different path reaches that same index with the same "last picked" value, so the same sub-problem gets solved over and over.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        return solve(0, -1);
    }

    private int solve(int i, int prev) {
        if (i == nums.length) return 0;
        int skip = solve(i + 1, prev);
        int take = 0;
        if (prev == -1 || nums[i] > nums[prev]) {
            take = 1 + solve(i + 1, i);
        }
        return Math.max(skip, take);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Let dp[i] hold the length of the longest increasing subsequence that ends exactly at index i. On its own, every index is a subsequence of length 1, so every entry starts at 1. To grow dp[i] further, look back at every earlier index j: whenever nums[j] is smaller than nums[i], the run ending at j can be extended by nums[i], giving a candidate length of dp[j] + 1. Taking the best such candidate across all valid j — and defaulting to 1 when none qualify — fills in dp[i] using only entries that were already finalized earlier in the pass. The answer is whichever dp[i] ends up largest, since the longest increasing subsequence overall has to end somewhere.

TimeO(n²)