AcWing 896. 最长上升子序列 II-JavaScript
原题链接
中等
作者:
semicloud
,
2024-03-04 19:27:15
,
所有人可见
,
阅读 24
const fs = require('fs');
const it = fs.readFileSync(0, 'utf-8').split('\n')[Symbol.iterator]();
const n = parseInt(it.next().value);
const a = [0, ...it.next().value.split(' ').map((x) => parseInt(x))];
const b = [a[1]];
// 二分,找到arr中第一个大于target的数的位置
function find(arr, target) {
let [l, r] = [0, arr.length - 1];
while (l < r) {
const mid = l + r >> 1;
if (arr[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
for (let i = 1; i <= n; ++i) {
if (a[i] > b[b.length - 1]) {
b.push(a[i]);
} else {
const j = find(b, a[i]);
b[j] = a[i];
}
}
console.log(b.length);