Ամենամեծ գումար ունեցող ենթազանգված (Maximum sum subarray)
Ձեզ տրված է
n ամբողջ թվերից բաղկացած զանգված. անհրաժեշտ է գտնել այն հարակց contiguous ենթազանգվածը, որի արժեքների գումարը ամենամեծն է:Մուտք
Մուտքի առաջին տողում տրված է
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: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB