LIS Length
Python
Hard
2 views
Problem Description
Read n integers. Output length of longest increasing subsequence.
Input Format
First line n. Second line n integers.
Output Format
One integer length.
Sample Test Case
Input:
8
10 9 2 5 3 7 101 18
Official Solution
import sys,bisect
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
d=[]
for x in a:
i=bisect.bisect_left(d,x)
if i==len(d):
d.append(x)
else:
d[i]=x
sys.stdout.write(str(len(d)))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!