Maximum Subarray Sum

Given a non-empty list of integers, your task is to find the maximum sum of any contiguous subarray. The solution must perform error checking to ensure that the input is a non-empty list of integers. If the input does not meet these requirements, an exception should be raised.

This problem can be efficiently solved using Kadane's algorithm. The key recurrence is given by:

$$current\_sum = \max(num, current\_sum + num)$$
$$max\_sum = \max(max\_sum, current\_sum)$$

Your program should read from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line of input contains an integer n, representing the number of elements in the list. The second line contains n space-separated integers.

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray.## sample

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

6