Maximum Subarray Sum

Given an array of integers, the task is to find the sum of the contiguous subarray (containing at least one number) which has the largest sum. This is a classical problem that can be solved using Kadane's algorithm.

Let the input array be \(A = [a_1, a_2, \dots, a_n]\). The idea is to maintain a variable \(curr\) which represents the maximum subarray sum ending at the current index, and a variable \(max\) which is the global maximum. The recurrence is given by:

[ curr = \max(a_i, curr + a_i) \quad \text{for } i = 1, 2, \dots, n ]

If the array is empty, the answer is defined to be 0. Otherwise, output the computed maximum subarray sum.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single non-negative integer \(n\), representing the number of elements in the array.
• If \(n > 0\), the second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), the second line is omitted.

outputFormat

Output a single integer to standard output (stdout), which is the maximum sum of any contiguous subarray of the given array.

9
-2 1 -3 4 -1 2 1 -5 4

6