I Hate Ready to Program P6 - Slash, Slash, Click

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

You stare at your MyCreation. You fixed all the syntax errors, but now it seems you have messed something up elsewhere! You want to see if you can comment out some of your N lines of code to determine which lines are the trouble-makers. However, to your horror, as you press the Ctrl+/ keys, nothing gets commented! You hear that Smth has said something along the lines of trying Ctrl+5, but that doesn't work either. You settle on painfully commenting out all consecutive lines within a certain range one line at a time. Each one of your N lines in your program has a purpose value, p. By commenting that line out, you remove p from the total purpose value of the program (which is the sum of all the purpose values of the non-commented lines). What is the maximum purpose value you can increase your program by, by commenting out consecutive lines in your program?

Constraints

1 \leq N \leq 10^7

-100 \leq p_i \leq 100

Subtask 1 [30%]

1 \leq N \leq 10^3

Subtask 2 [70%]

No further constraints.

Input Specifications

The first line will contain an integer, N.

The next line will contain N space-separated integers, p_1,p_2,p_3,...,p_N, signifying the purpose value of each line in your program.

Output Specifications

Output one number, v, the maximum purpose value you can increase your program by.

Sample Input

7
-2 -6 10 5 -3 -7 -4

Sample Output

14

Sample Case Explanation

By taking the 5th, 6th, and 7th lines and commenting them out, we subtract -3, -7, and -4 from the total, which actually INCREASES our program's purpose value by 14 (since we are subtracting negative numbers). Notice that we cannot comment out lines 1 and 2 along with 5, 6, and 7 since that would also involve commenting out lines 3 and 4, bringing the total increase to only +7.

Also, you're asking yourself why most of your program serves no purpose.


Comments

There are no comments at the moment.