Maximum Subarray Sum

Given an array of N integers, find the maximum sum of any contiguous subarray. This problem can be efficiently solved using Kadane's algorithm. The key idea of Kadane's algorithm is to compute the maximum subarray sum ending at each index and then take the maximum among these sums.

The recurrence relation is given by:

$$ max\_ending\_here = \max(a_i, max\_ending\_here + a_i) $$

where a_i is the current element. The final answer is the maximum of all max_ending_here values.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer N — the number of elements in the array.
• The second line contains N space-separated integers representing the array elements.

outputFormat

Output the maximum sum of any contiguous subarray to stdout.

5
1 2 3 -2 5

9