Longest Increasing Subsequence 2
Տրված է
n ամբողջ թվերից կազմված զանգված. Ձեր խնդիրը կլինի գտնել զանգվածի ամենաերկար աճող ենթահաջորդականությունը: Եթե קיימում են մի քանի հնարավոր ամենաերկար աճող ենթահաջորդականություններ, կարող եք տպել դրանցից ցանկացածը:Զանգվածի ենթահաջորդականություն կարելի է ստանալ՝ հեռացնելով որոշ (հնարավոր է նաև ոչ մեկ) տարրեր, առանց փոխելու մնացած տարրերի հաջորդականությունը: Օրինակ, եթե զանգվածը է, ապա -ը -ի ենթահաջորդականություն է, իսկ -ը ենթահաջորդականություն չէ, քանի որ սկզբնական տարրերի կարգը խախտվել է:
💡
Աճող ենթահաջորդականություն կոչվում է այն ենթահաջորդականությունը, որտեղ տարրերը դասավորված են աճման կարգով: Օրինակ, եթե զանգվածը է, ապա -ը -ի աճող ենթահաջորդականություն է, իսկ -ը աճող ենթահաջորդականություն չէ, քանի որ տարրերը աճման կարգով դասավորված չեն:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000), որը զանգվածի երկարությունն է:Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր (), որոնք կազմում են զանգվածի տարրերը:Ելք
Ծրագիրը ելքում պետք է տպի զանգվածի ամենաերկար աճող ենթահաջորդականության երկարությունը:
Օրինակներ
Մուտք | Ելք |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Բացատրություն
- Առաջին օրինակում զանգվածի ամենաերկար աճող ենթահաջորդականությունը է:
- Երկրորդ օրինակում զանգվածի ամենաերկար աճող ենթահաջորդականությունը է:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB