UVa 12640: Largest Sum Game (Solution)

19:20:00 Multiple PC World 0 Comments

Largest Sum Game

After a long beer party and when ready for the check, John and his friends play the largest sum game and whoever wins the game will not have to pay a dime of the check. The largest sum game consists in finding the largest sum of consecutive values in a sequence of numbers; the winner is the one quickest to answer.

For example, in the sequence 23,−1,−24, 2, 23 the largest sum of consecutive values is 25 and whoever finds this value first, is the winner of the game.

Although simple (and geeky), the game is challenging because beer and arithmetic do not mix well together. However, since the group of friends are amateur programmers, each have implemented an algorithmic solution for finding the largest sum and have agreed to select the winner of the game in the form of a programming challenge: they connect their laptops to a central server that produces a random sequence of numeric values, run the solutions on this data, and the program quickest to answer wins the game.

John is tired of paying night after night without ever winning the game and he is determined to stop this situation tonight. John has hired you to write a highly efficient computer program that could beat the others in the largest sum game.

Input

The input consists of several test cases, each one dened by a line containing a sequence of N blank-separated integers x1, x2, ... ,xN (1 ≤ N ≤ 10^5, -10^3 ≤ xi ≤ 10^3 for each 1 ≤ i ≤ N)

The input must be read from standard input.

Output

For each test case, output a line with the largest sum of consecutive values in x1, x2, . . . , xN.

The output must be written to standard output.

Sample Input

1 2 3 4 5 6 7 8 9
-1 -1 -1
23 -1 -24 2 23
1 -14 -4 14 -11 -7

Sample Output

45
0
25
14

SOLUTION: Python