Առավելագույն գումարով ենթազանգված Բաժանիր և տիրիր ալգորիթմով
Տրված է 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) = 71 -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