Maximum Subarray Sum

Given an array of integers (which may include both positive and negative numbers), find the contiguous subarray (containing at least one number) that has the largest sum and output that sum.

The optimal solution is based on Kadane's algorithm which operates in \(O(n)\) time. The recurrence relation used by the algorithm is:

\(dp[i] = \max(a_i, dp[i-1] + a_i)\)

Edge cases include arrays with all negative numbers, where the maximum subarray is the single largest element, and empty arrays, for which the answer should be 0.

inputFormat

The first line of input contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers. If (n = 0), the array is considered empty.

outputFormat

Output a single integer which is the maximum subarray sum.## sample

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

6