fork download
copy 
  1. n = int(input())
  2. a = list(map(int,input().split()))
  3. dp = [a[0]]
  4. for i in range(1,n):
  5.     if a[i] > dp[-1]:
  6.         dp.append(a[i])
  7.     else:
  8.         st = 0
  9.         en = len(dp) - 1
  10.         mi = (st+en)//2
  11.         while True:
  12.             if a[i] > dp[mi]:
  13.                 st = mi
  14.             elif a[i] < dp[mi]:
  15.                 en = mi
  16.             else:
  17.                 break
  18.             if en - st <= 1:
  19.                 if dp[st] != a[i]:
  20.                     dp[en] = a[i]
  21.                 break
  22.             mi = (st+en) // 2
  23. print(len(dp))
Success #stdin #stdout 0.01s 27696KB
comments (?)
stdin
copy 
8
10 20 30 5 10 20 30 40
stdout
copy 
6
https://ideone.com/gMubmj
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!