Երկարագույն աճող ենթահաջորդականություն 1
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n ամբողջ թվերից բաղկացած զանգված, պարզի այդ զանգվածի առավել երկար աճող ենթահաջորդականությունը։ Եթե կան մի քանի հավասար երկարություն ունեցող ենթահաջորդականություններ, կարող եք ցուցադրել դրանցից որևէ մեկը։Ենթահաջորդականությունը որոշվում է զանգվածից որոշ (հնարավոր է զրո) էլեմենտներ ջնջելով, առանց փոխելու մնացած էլեմենտների հերթականությունը։ Օրինակ, եթե զանգվածը է, ապա -ը -ի ենթահաջորդականություն է, իսկ -ը չէ, քանի որ այստեղ էլեմենտների սկզբնական հերթականությունը չի պահպանվում։
💡
Աճող ենթահաջորդականությունը այն ենթահաջորդականությունն է, որտեղ էլեմենտները դասավորված են աճման կարգով։ Օրինակ, եթե զանգվածը է, ապա -ը -ի աճող ենթահաջորդականություն է, իսկ -ը չէ, քանի որ էլեմենտները աճող կարգով չեն դասավորված։
Մուտք
Մուտքիแรก տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 1000)։Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր (1 ≤ ≤ 10^9), որոնք ներկայացնում են զանգվածի էլեմենտները։Ելք
Ծրագիրը պետք է տպի զանգվածի առավել երկար աճող ենթահաջորդականության երկարությունը։
Օրինակներ
Մուտք | Ելք |
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