Երկարագույն աճող ենթահաջորդականություն 1
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n ամբողջ թվերից բաղկացած զանգված, պարզի այդ զանգվածի առավել երկար աճող ենթահաջորդականությունը։ Եթե կան մի քանի հավասար երկարություն ունեցող ենթահաջորդականություններ, կարող եք ցուցադրել դրանցից որևէ մեկը։
Ենթահաջորդականությունը որոշվում է զանգվածից որոշ (հնարավոր է զրո) էլեմենտներ ջնջելով, առանց փոխելու մնացած էլեմենտների հերթականությունը։ Օրինակ, եթե զանգվածը է, ապա -ը -ի ենթահաջորդականություն է, իսկ -ը չէ, քանի որ այստեղ էլեմենտների սկզբնական հերթականությունը չի պահպանվում։
Մուտք
Մուտքիแรก տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000)։
Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր (1 ≤ ≤ 10^9), որոնք ներկայացնում են զանգվածի էլեմենտները։
Ելք
Ծրագիրը պետք է տպի զանգվածի առավել երկար աճող ենթահաջորդականության երկարությունը։
Օրինակներ
Մուտք | Ելք |
|---|---|
8 | 5 |
6 | 3 |
Պարզաբանում
Առաջին օրինակում զանգվածի առավել երկար աճող ենթահաջորդականությունը -ն է։
Երկրորդ օրինակում առավել երկար աճող ենթահաջորդականությունը -ն է։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB