Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. If the array is empty or if all elements are negative, the answer is 0.

One efficient approach is using Kadane's algorithm. The recurrence relation used in this algorithm is given by:

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

The answer is then the maximum value among all dp[i].

Note that the contiguous subarray must be non-empty; however, if all numbers are negative, output 0 instead.

inputFormat

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

outputFormat

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

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

6