Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum possible sum of any non-empty contiguous subarray. This classic problem can be solved efficiently using Kadane's algorithm.

For an array a of length n, a subarray is defined as a contiguous segment of the array. The maximum subarray sum is the largest sum of any such segment. Note that the array may contain both positive and negative integers; if all numbers are negative, the maximum subarray sum is the largest (least negative) number.

The input will consist of multiple test cases. For each test case, the first number indicates the number of elements in the array, followed by a line containing these integers separated by spaces. A test case starting with 0 indicates the termination of input.

Your solution should read from standard input (stdin) and write the results for each test case to standard output (stdout), each on a new line.

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case is composed as follows:

• The first line contains an integer n (n > 0), representing the number of elements in the array.
• The second line contains n integers separated by spaces, representing the array elements.

A test case where n is 0 indicates the end of input and should not be processed.

outputFormat

For each test case, output the maximum subarray sum on a separate line to stdout.

## sample

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

3
5
4

</p>