What it teaches: The quadratic DP, then the tails array with binary search.
Practise it on judges as “Longest Increasing Subsequence”.
The problem
Return the length of the longest strictly increasing subsequence.
Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
[2, 3, 7, 101].
Constraints
1 ≤ n ≤ 2500
Pattern clues in the wording
→ Longest increasing subsequence (not contiguous)
These clues point to Longest Increasing Subsequence: dp[i] is the longest increasing run ending at i; a patience-sorting version with binary search gets O(n log n).
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int lengthOfLIS(int[] nums) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
For each i, look back at all j < i with nums[j] < nums[i].
Approach 1
import java.util.Arrays;
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length, best = 1;
int[] dp = new int[n];
Arrays.fill(dp, 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);
best = Math.max(best, dp[i]);
}
return best;
}
}
Verdict: Easy to extend (count LIS, reconstruct).
2
Tails + binary search
Time O(n log n) Space O(n)
For each x, lower-bound in tails; replace or append.
Approach 2
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
}
Verdict: Optimal.
Before you submit
Edge cases and common mistakes
Test these inputs
All equal (1)
Strictly decreasing (1)
Already sorted (n)
Mistakes people make
Using upper bound (allows equal values, i.e. non-decreasing).