Longest Increasing Subsequence
Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
nums = [10,9,2,5,3,7,101,18]4tails where tails[k] is the smallest possible last value of an increasing subsequence of length k+1. For each x, replace the first tail ≥ x with x (or append). The length of tails at the end is the LIS length.from bisect import bisect_left
def length_of_lis(nums):
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)function lengthOfLIS(nums) {
const tails = [];
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
if (lo === tails.length) tails.push(x);
else tails[lo] = x;
}
return tails.length;
}class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int x : nums) {
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails.get(mid) < x) lo = mid + 1; else hi = mid;
}
if (lo == tails.size()) tails.add(x);
else tails.set(lo, x);
}
return tails.size();
}
}int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
}Explanation
We want the length of the longest strictly increasing subsequence. This solution uses a slick O(n log n) trick built around an array called tails, where tails[k] is the smallest possible ending value of any increasing subsequence of length k+1.
The key insight: keeping each length's tail as small as possible leaves the most room to extend later. The tails array always stays sorted, which lets us use binary search.
For each number x, we use bisect_left to find the first tail that is >= x. If there is none, x extends the longest run so far, so we append it. Otherwise we overwrite that tail with x, lowering it without changing any lengths.
The final answer is simply len(tails). Note tails is not the actual subsequence — just a bookkeeping device whose length matches the LIS length.
Example: nums = [10,9,2,5,3,7,101,18]. The tails evolve toward [2,3,7,18], ending with length 4, the answer.