Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence. You may skip values, but must preserve their original order.
Work through the cases
3 examplesInput notation
Space-separated integers on one line.Expected result
The maximum subsequence length.Case 1
Input
5 1 4 2 3
Expected output
3
Case 2
Input
7 7 7
Expected output
1
Case 3
Input
-3 -2 -1
Expected output
3
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A subsequence must keep relative order and increase strictly. Enumerating all subsequences explodes with n; n ≤ 2500 still allows an O(n^2) transfer by ending index. The LIS ending at nums[i] depends only on smaller values to its left. Define f[i] as that length, and for each j < i with nums[j] < nums[i] take \max(f[j]+1). A singleton has length 1, and the answer is \max f.
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] f = new int[n];
Arrays.fill(f, 1);
int ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.