Length of LIS
JavaScript
Hard
5 views
Problem Description
Find length of the Longest Increasing Subsequence (not necessarily contiguous).
Input Format
One line: n then n integers.
Output Format
One integer length.
Sample Test Case
Input:
8 10 9 2 5 3 7 101 18
Official Solution
const fs=require('fs');const p=fs.readFileSync(0,'utf8').trim().split(/\\s+/);if(!p[0])process.exit(0);let i=0;const n=Number(p[i++]);let tails=[];for(let j=0;j<n;j++){const x=Number(p[i++]);let l=0,r=tails.length;while(l<r){const mid=(l+r)>>1;if(tails[mid]<x)l=mid+1;else r=mid;}tails[l]=x;}process.stdout.write(String(tails.length));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!