Maximum Subarray Sum

You are given a sequence of n integers representing the difficulty levels of cities along a route. Your task is to find the maximum sum of any contiguous subsequence using Kadane's Algorithm.

More formally, given a sequence \( a_1, a_2, \ldots, a_n \), you need to compute the maximum possible value of a sum for some contiguous subarray \( a_i + a_{i+1} + \cdots + a_j \) (where \(1 \leq i \leq j \leq n\)). The recurrence relation used in Kadane's algorithm can be written in LaTeX as:

\[ max\_current = \max(a_i, max\_current + a_i) \]

and the global maximum is updated accordingly.

Assume that the array contains at least one element.

inputFormat

The input is given via stdin and has the following format:

1. The first line contains a single integer n which represents the number of cities.
2. The second line contains n space-separated integers, representing the difficulty levels of the cities.

outputFormat

Output a single integer to stdout, which is the maximum sum achievable from any contiguous subarray of the given array.

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

6