Difficulty: Medium1-D Dynamic Programming

Longest Increasing Subsequence

Problem in Plain English

Given an integer array, find the length of the longest subsequence whose values rise strictly from left to right.

Problem Statement

You are given an integer array nums. A subsequence keeps some elements in their original order while deleting the rest.

Return the length of the longest subsequence that is strictly increasing. The subsequence itself need not be contiguous, and equal values never extend a strictly rising run.

Constraints

$1 \leq \text{nums.length} \leq 2500$
$-10^4 \leq \text{nums}[i] \leq 10^4$

Examples

Example 1

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

Skip 3 and keep indices 1 and 2, giving [1, 2]. Keeping 3 prevents either later pick, and the entire array is not increasing, so the maximum length is 2.

Example 2

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

Indices 2, 4, 5 and 6 give [2, 3, 7, 101]; choosing index 7 instead of 6 also gives [2, 3, 7, 18]. A length-5 subsequence is impossible: after choosing 2, at most one of 5 and 3 can be kept, followed by 7 and at most one of 101 and 18.

Example 3

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

Indices 0, 1, 4 and 5 give [0, 1, 2, 3]. The earlier 3 at index 3 must be skipped to use the later 2. Repeated 0 and 3 values cannot themselves extend a strictly increasing subsequence, so the answer is 4.

Example 4

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

No pair of positions has a strictly larger second value. Every single 7 is valid, but adding another 7 would violate strict increase, so the answer is 1.

Example 5

Input: nums = [-10000]
Output: 1

The sole negative value forms a subsequence of length 1. A starting sentinel of 0 would incorrectly forbid this value; an index of -1 represents no previous pick.

Intuition

A subsequence may skip positions, but it must keep their order. In Example 1, keeping 3 blocks both later values, while skipping it lets us keep [1, 2]. Enumerating picks and skips discovers this length, but many branches ask the same future question. For a given length, a smaller final value is always at least as easy to extend: ending at 1 instead of 3 preserves the chance to use a later 2. The fast method remembers only that smallest tail for each possible length, rather than every subsequence.

Approaches

Recursive Pick Or Skip

Solution Details

Reveal Recursive Pick Or Skip: intuition, complexity, and code

Intuition

At each index, every valid subsequence either skips this value or picks it after a smaller previous pick. Remember the previous index, with -1 meaning no pick yet, and return the larger remaining length from the legal alternatives. This is an intentionally uncached baseline: it makes the search exhaustive but repeats equivalent suffix states.

Step-by-Step Logic

Define dfs(i, prev) as the best additional length from the suffix; return 0 when i reaches n. Start Example 1, nums = [3, 1, 2], with dfs(0, -1).
Always compute the skip branch dfs(i + 1, prev). Compute the pick branch only if prev is -1 or nums[i] > nums[prev], adding 1 for the current value.
Return max(skip, pick), preserving prev on a skip and passing i on a pick. Skipping 3 lets the suffix pick 1 and 2; keeping 3 blocks both later values.
Compare the two root alternatives: skip returns 2 and pick returns 1. Return 2. The table follows the actual skip-first execution order, recording every call and return, including base cases.

Why It Works

Let dfs(i, prev) return the largest number of additional picks from index i onward after the fixed previous pick. At i = n no positions remain, so the answer is 0. Every valid continuation either excludes nums[i], represented by dfs(i + 1, prev), or includes it. Inclusion is legal exactly when there is no previous pick or nums[i] exceeds nums[prev]; its answer is 1 + dfs(i + 1, i). These disjoint alternatives cover every valid continuation. Taking their maximum therefore gives the best length, by induction on the remaining suffix length. The initial call has no previous pick and covers the whole array.

Dry Run

Recursive Pick Or Skip: variable states at each step
event / call	parent / branch	i	prev index / value	skip	pick including current	returned length
enter 1	root / start	0	none	pending	pending	pending
enter 2	1 / skip	1	none	pending	pending	pending
enter 3	2 / skip	2	none	pending	pending	pending
enter 4	3 / skip	3	none	pending	pending	pending
return 4	base case	3	none	-	-	0
enter 5	3 / pick	3	2 / 2	pending	pending	pending
return 5	base case	3	2 / 2	-	-	0
return 3	2 / skip	2	none	0	1	1
enter 6	2 / pick	2	1 / 1	pending	pending	pending
enter 7	6 / skip	3	1 / 1	pending	pending	pending
return 7	base case	3	1 / 1	-	-	0
enter 8	6 / pick	3	2 / 2	pending	pending	pending
return 8	base case	3	2 / 2	-	-	0
return 6	2 / pick	2	1 / 1	0	1	1
return 2	1 / skip	1	none	1	2	2
enter 9	1 / pick	1	0 / 3	pending	pending	pending
enter 10	9 / skip	2	0 / 3	pending	pending	pending
enter 11	10 / skip	3	0 / 3	pending	pending	pending
return 11	base case	3	0 / 3	-	-	0
return 10	9 / skip	2	0 / 3	0	blocked	0
return 9	1 / pick	1	0 / 3	0	blocked	0
return 1	root / start	0	none	2	1	2

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be nums.length. A strictly increasing array permits both choices at every node, producing 2^(n+1) - 1 calls, hence O(2^n) worst-case time. Each call stores only indices and scalar branch results; at most n + 1 frames coexist, so auxiliary space is O(n), with no memo table, copied subsequences or input mutation. This baseline is unsuitable for general n = 2500 inputs because of exponential time. Descending or equal inputs have only O(n²) calls and can test the maximum depth. Python temporarily raises and restores its recursion limit; Java and JavaScript may require a larger runtime stack. Prefer tails for predictable performance at the stated maximum.

Code

Solution.java

1class Solution {2    public int lengthOfLIS(int[] nums) {3        return dfs(nums, 0, -1);4    }5
6    private int dfs(int[] nums, int i, int prev) {7        if (i == nums.length) return 0;8        int skip = dfs(nums, i + 1, prev);9        int pick = 0;10        // -1 is an index sentinel: every integer value may be the first pick.11        if (prev == -1 || nums[i] > nums[prev]) {12            pick = 1 + dfs(nums, i + 1, i);13        }14        return Math.max(skip, pick);15    }16}

Hints

Hint 1

Fix the end first: the best run ending at each position extends the best compatible run before it.

Hint 2

For the faster method, track per length the smallest tail any run of that length can end with.

Hint 3

Tails stay sorted, so each value extends the runs or binary-searches the first tail at or above it and lowers that tail.

Edge Cases

All equal values like [7, 7, 7] return 1 since rises must be strict.
A fully descending array returns 1; every value only replaces the length-1 tail.
A fully ascending array extends on every value and returns n.
A minimum-bound value such as [-10000] still starts a length-1 subsequence; no previous index is different from a previous value of zero.
For [2, 3, 1], final tails is [1, 3], but 1 occurs after 3 and cannot precede it in a subsequence. The returned length 2 is correct via [2, 3]; the stored entries need not form a witness.

Common Mistakes and Interview Tips

Using >= instead of > when extending lets equal values chain and overcounts runs like [2, 2].
Returning the tails contents as the run itself; only its length is guaranteed, not its members.
Binary-searching for the value instead of its lower bound replaces the wrong tail on duplicates.
Sorting nums destroys original order: [3, 2, 1] has LIS length 1 even though its sorted values have length 3.
Searching all allocated Java tails slots reads unused zeros; restrict right to size - 1.
Presenting uncached recursion as viable for 2500 elements overlooks both exponential work and call-stack limits. In an interview, explain this limitation before choosing the fast method.

Key Takeaway

When subsequence length only cares about the best tail per length, maintain those tails in sorted order and place each element with binary search for a near-linear solution.