Max Growth Index

Given a sequence of integers representing the growth indices of cells in a reef, determine the maximum total growth index for any contiguous subsegment. This is a classic application of Kadane's algorithm.

The contiguous subsegment could be as small as a single cell. You will be provided with an integer n representing the number of cells, followed by n space-separated integers indicating the growth index for each cell. Your task is to compute and output the maximum possible sum obtained from any contiguous subsegment.

Formally, if the growth indices are given by \(a_1, a_2, \ldots, a_n\), find the maximum value of \(\sum_{i=l}^{r} a_i\) for any \(1 \le l \le r \le n\).

inputFormat

The first line contains an integer (n), the number of cells in the reef. The second line contains (n) space-separated integers representing the growth indices.

outputFormat

Output a single integer denoting the maximum total growth index for any contiguous subsegment.## sample

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

6