Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ամենամեծ գումար ունեցող ենթազանգված

Ձեզ տրված է n ամբողջ թվերից բաղկացած զանգված։ Անհրաժեշտ է գտնել այն շարունակական ենթազանգվածը, որի արժեքների գումարը ամենամեծն է:

Մուտք

Մուտքի առաջին տողում տրված է 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

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

  1. -2 1 -3 4 -1 3 1 -4 -2 → Նշված ենթազանգվածի գումարը (4 - 1 + 3 + 1) = 7

  2. 1 -2 3 4 -3 1 7 -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12

Կարո՞ղ ես դա էլ ավելի լավ դարձնել 😎:

Հնարավոր է լուծել այս խնդիրը առանց լրացուցիչ զանգվածներ օգտագործելու։ Կարո՞ղ ես անել դա:

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 1 MB

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