Ամենաերկար աճող ենթահաջորդականություն առավելագույն գումարով

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n ամբողջ թվերից բաղկացած զանգված, կգտնի զանգվածի ամենաերկար աճող ենթահաջորդականությունը: Եթե գոյություն ունեն մի քանի նման ենթահաջորդականություններ, կարող եք տպել դրանցից որևէ մեկին:

Էնթահաջորդականությունը ձևավորվում է զանգվածից որոշ (հնարավոր է՝ զրո) էլեմենտներ հեռացնելով, առանց խախտելու մնացած էլեմենտների հերթականությունը: Օրինակ, եթե զանգվածը է, τότε -ի ենթահաջորդականություն է, իսկ -ը չէ, քանի որ էլեմենտների հերթականությունը խախտվել է:

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000), որը ներկայացնում է զանգվածի երկարությունը:

Երկրորդ տողում տրված են n տարածությամբ բաժանված թվեր (), որոնք հանդիսանում են զանգվածի էլեմենտները:

Ելք

Ծրագիրը պետք է տպի առավելագույն գումարով ամենաերկար աճող ենթահաջորդականության գումարը:

Մուտք

Ելք

8
1 3 2 4 5 2 6 5

19

6
10 9 2 5 3 7

14

Բացատրություն

  1. Առաջին օրինակով առավելագույն գումարով ամենաերկար աճող ենթահաջորդականությունը է։

  2. Երկրորդ օրինակով առավելագույն գումարով ամենաերկար աճող ենթահաջորդականությունը է։

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue