A subsequence keeps order but need not be contiguous. [2, 5, 3, 7] has [2, 5, 7] and [2, 3, 7] as increasing subsequences of length 3. A subarray would have to be a block — [5, 3] is a subarray and is not increasing.
You want the length of the longest *strictly* increasing subsequence (LIS). Reconstructing one of the sequences is extra bookkeeping; the arena asks for the length only.
function lengthOfLIS(nums) {
const n = nums.length;
const dp = Array(n).fill(1);
let best = 1;
for (let i = 0; i < n; i++) {
for (let 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 n === 0 ? 0 : best;
}dp[i] is the longest increasing subsequence that ends at index `i`. Scan every j < i with nums[j] < nums[i] and extend. Base 1 (the element alone). Answer is max(dp).
n = 2·10³ makes n² comfortable; n = 10⁵ does not. Then you need the tails trick.
Patience / tails, O(n log n) sketch. Keep an array tails where tails[len] is the smallest tail value of any increasing subsequence of length len + 1 seen so far. tails stays sorted.
For each x in nums:
1. Binary search the first index in tails whose value is ≥ x (strict LIS: lower bound).
2. If x is larger than every tail, append it — you grew the LIS.
3. Otherwise replace that tail with x. You did not shrink the answer; you made that length cheaper to extend later.
The length of tails is the LIS length. The array itself is not an LIS (replacements scramble it). Reconstructing a sequence needs parent pointers; skip that until a problem asks.
function lengthOfLISFast(nums) {
const tails = [];
for (const x of nums) {
let lo = 0;
let hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
}
return tails.length;
}Checks 0/2