Find the contiguous, non-empty subarray with the largest sum and return that sum.
Input: one line of space-separated integers. Output: the maximum subarray sum.
Your program reads from stdin and prints to stdout.
Example 1
Input: -2 1 -3 4 -1 2 1 -5 4
Output: 6
Hints