Maximum Subarray Sum

Given an array of integers, find the contiguous subarray within the array which has the largest sum. This is a classic problem known as the Maximum Subarray Problem and can be efficiently solved using Kadane's Algorithm.

The key recurrence used in this algorithm is given by the formulas:

\(\text{max_current} = \max(\text{num}, \text{max_current} + \text{num})\)

\(\text{max_global} = \max(\text{max_global}, \text{max_current})\)

These formulas ensure that at each step, we keep track of the maximum subarray sum ending at the current position, and update the overall maximum when needed.

inputFormat

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10⁶), representing the number of elements in the array. The second line contains n space-separated integers which can be both positive and negative.

outputFormat

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

5
1 2 3 4 5

15