Maximum Contiguous Subsequence Sum

Given an array of integers, the task is to find the maximum sum of any contiguous subsequence. This problem is often solved using Kadane's Algorithm, which runs in O(n) time. The recurrence used in Kadane's Algorithm is given by: $$current\_max = \max(a_i, current\_max + a_i)$$ and $$overall\_max = \max(overall\_max, current\_max)$$, where \(a_i\) is the i-th element of the array.

If all integers are negative, the answer is the largest (i.e., the least negative) element.

The input will consist of multiple test cases provided on separate lines. Each test case starts with an integer indicating the number of elements in the array, followed by the elements themselves. The input ends when a line starts with 0.

inputFormat

The input is given via standard input (stdin) and consists of multiple test cases. Each test case is provided on its own line. The first integer of a line is \(n\), specifying the number of elements in that test case, followed by \(n\) space-separated integers. The sequence of test cases ends when a line begins with the integer 0.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum contiguous subsequence sum.

9 -2 1 -3 4 -1 2 1 -5 4
0

6