Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray within the given array. This is a classic problem often solved using Kadane's algorithm. The recurrence used in the algorithm is given by \(dp[i] = \max(a_i, dp[i-1] + a_i)\), where \(a_i\) represents the \(i^{th}\) element of the array.

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6, corresponding to the subarray [4, -1, 2, 1].

inputFormat

The input is read from stdin. The first line contains an integer \(n\) which denotes the number of elements in the array. The second line contains \(n\) space-separated integers representing the array.

outputFormat

Output a single integer to 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