Առավելագույն գումարով ենթազանգված Բաժանիր և տիրիր ալգորիթմով
Տրված է
n ամբողջ թվերից բաղկացած զանգված։ Օգտագործելով Բաժանիր և տիրիր (Divide & Conquer) մեթոդը, գտեք այն հարակից ենթազանգվածը, որի գումարը կունենա հնարավոր առավելագույն արժեք։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը — զանգվածի տարրերի քանակը (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր, որոնք բաժանված են բացատով և ներկայացնում են զանգվածի տարրերը ։Ելք
Ծրագիրը պետք է տպի մեկ ամբողջ թիվ — ամենամեծ հնարավոր գումարը, որը կարելի է ստանալ զանգվածի որեւէ ենթազանգվածից։
Օրինակներ
Մուտք | Ելք |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Բացատրություն
- -2 1 -3
4 -1 3 1-4 -2 → ընդգծված ենթազանգվածի գումարը (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB