Maximum Subarray Sum

You are given an array of n integers representing the fertility levels of fields. Your task is to compute the maximum sum of any contiguous subarray from these fields.

This problem can be solved using Kadane's algorithm. In this method, we update the current running sum using the formula: \(current = \max(a_i, current + a_i)\). The answer is the maximum value encountered during this process.

If all numbers are negative, the answer is the maximum (least negative) number in the array.

inputFormat

The first line contains an integer n representing the number of fields. The second line contains n space-separated integers representing the fertility levels of the fields.

outputFormat

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

5
-3 4 -1 2 1

6