Գտնել ամենաերկար աճող ենթահաջորդականությունը
Տեղարկված է
n ամբողջ թվերից բաղկացած զանգված։ Պետք է գտնել այդ զանգվածի ամենաերկար աճող ենթահաջորդականությունը։ Եթե կան մի քանի նման ենթահաջորդականություններ, կարող եք տպել դրանցից ցանկացածը։Զանգվածի ենթահաջորդականությունը ձևավորվում է որոշ (հնարավոր է նաև ոչ մի) էլեմենտներ հեռացնելով, առանց փոփոխելու մնացած էլեմենտների սկզբնական հերթականությունը։ Օրինակ, եթե զանգվածը է, então -ը ենթահաջորդականություն է, իսկ -ը ենթահաջորդականություն չէ, քանի որ հեռացվող և մնացող էլեմենտների հերթականությունը խախտվել է։
💡
Աճող ենթահաջորդականությունը զանգվածի այն ենթահաջորդականությունն է, որի էլեմենտները դասավորված են աճող կարգով։ Օրինակ, եթե զանգվածը է, ապա -ը աճող ենթահաջորդականություն է, իսկ -ը աճող ենթահաջորդականություն չէ, քանի որ էլեմենտները չեն գնում աճող հերթականությամբ։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000), որը սահմանում է զանգվածի երկարությունը։Մուտքի երկրորդ տողում տրված են
n լրացուցիչ ամբողջ թվեր (), որոնք համապատասխանաբար ներկայացնում են զանգվածի էլեմենտները։Ելք
Ելքի առաջին տողում պետք է տպվի մեկ ամբողջ թիվ
k — ամենաերկար աճող ենթահաջորդականության երկարությունը։Ելքի երկրորդ տողում պետք է տպվեն այդ ենթահաջորդականության
k էլեմենտները հերթականությամբ։ Եթե կան մի քանի ճիշտ պատասխաններ, կարող եք տպել դրանցից որևէ մեկը։Օրինակներ
Մուտք | Ելք |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Նշում
Երկրորդ օրինակով ևս մեկ հնարավոր աճող ենթահաջորդականություն է , որը նույնպես ունի երկարություն 3։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB