Longest Increasing Subsequence
Problem
Return the length of the longest strictly increasing subsequence of nums.
Input
nums = [10,9,2,5,3,7,101,18]Output
4Maintain
tails 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 lis_length(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();
}