Maximum Segment Sum

You are given an array of integers. Your task is to find a contiguous subarray (segment) with the maximum possible sum. This is a classic problem that can be solved efficiently using Kadane's algorithm.

The input begins with an integer n representing the number of elements in the array. The next line contains n space-separated integers. You must output a single integer; the maximum sum obtainable from any contiguous segment. In case all numbers are negative, the answer is the largest (least negative) number.

The key idea behind the solution is to use the recurrence:

\( current = \max(a_i, current + a_i) \)

and update the maximum found so far accordingly.

inputFormat

The first line of input contains an integer n (\(1 \le n \le 10^5\)). The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\) where each \(a_i\) satisfies \(-10^9 \le a_i \le 10^9\).

outputFormat

Output a single integer – the maximum segment (subarray) sum.

5
1 -2 3 4 -1

7