Maximum Subarray Sum

The problem is to find the contiguous subarray within a one-dimensional array of numbers which has the largest sum. This subarray must contain at least one number.

For example, given an array \(nums = [3, -2, 5, -1]\), the contiguous subarray with the largest sum is \([3, -2, 5]\) which sums to 6. Similarly, for \(nums = [5, 4, -1, 7, 8]\), the entire array forms the subarray with the largest sum which is 23.

You are required to read the input from the standard input (stdin) and output the result to the standard output (stdout).

Note: If the array is empty, return 0.

inputFormat

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

outputFormat

Output a single integer, which is the sum of the contiguous subarray with the largest sum.

4
3 -2 5 -1

6