Ամենաերկար աճող ենթահաջորդականություն առավելագույն գումարով
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n ամբողջ թվերից բաղկացած զանգված, կգտնի զանգվածի ամենաերկար աճող ենթահաջորդականությունը: Եթե գոյություն ունեն մի քանի նման ենթահաջորդականություններ, կարող եք տպել դրանցից որևէ մեկին:Էնթահաջորդականությունը ձևավորվում է զանգվածից որոշ (հնարավոր է՝ զրո) էլեմենտներ հեռացնելով, առանց խախտելու մնացած էլեմենտների հերթականությունը: Օրինակ, եթե զանգվածը է, τότε -ը -ի ենթահաջորդականություն է, իսկ -ը չէ, քանի որ էլեմենտների հերթականությունը խախտվել է:
💡
Զանգվածի աճող ենթահաջորդականությունը ենթահաջորդականություն է, որի էլեմենտները դասավորված են աճման կարգով։ Օրինակ, եթե զանգվածը է, ապա -ը -ի աճող ենթահաջորդականություն է, իսկ -ը աճող ենթահաջորդականություն չէ, քանի որ էլեմենտները դասավորված չեն աճման կարգով։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 1000), որը ներկայացնում է զանգվածի երկարությունը:Երկրորդ տողում տրված են
n տարածությամբ բաժանված թվեր (), որոնք հանդիսանում են զանգվածի էլեմենտները:Ելք
Ծրագիրը պետք է տպի առավելագույն գումարով ամենաերկար աճող ենթահաջորդականության գումարը:
Մուտք | Ելք |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Բացատրություն
- Առաջին օրինակով առավելագույն գումարով ամենաերկար աճող ենթահաջորդականությունը է։
- Երկրորդ օրինակով առավելագույն գումարով ամենաերկար աճող ենթահաջորդականությունը է։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB