Maximum Subarray Sum

Given an array of integers, find the maximum sum of any contiguous subarray. The subarray should contain at least one element. Use Kadane's Algorithm to achieve an optimal solution. The answer may be negative if all numbers in the array are negative.

Note: The subarray must be contiguous. For example, for the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6.

inputFormat

The input consists of two lines. The first line contains a single integer n, the number of elements in the array. The second line contains n space‐separated integers representing the elements of the array.

outputFormat

Output a single integer denoting the maximum subarray sum.

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

6