Maximum Subarray Sum

Given a list of integers, your task is to compute the largest sum of any contiguous subarray using an efficient algorithm. The subarray must contain at least one element. For example, given the array [1, 2, 3, 4, 5], the maximum subarray sum is 15, since taking the entire array produces the maximum sum. If the array is empty, the answer is defined to be 0.

This problem can be solved in O(n) using Kadane's algorithm. Consider both positive and negative integers while processing the array.

inputFormat

The input is given in two lines. The first line contains a single integer n (n ≥ 0) which represents the number of elements in the array. The second line contains n space-separated integers. If n is 0, the second line may be empty.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray.

5
1 2 3 4 5

15