Largest Sum Subarray

Given an array of n integers, your task is to find the maximum possible sum of any non-empty contiguous subarray.

Mathematically, for an array \(A = [a_1, a_2, \dots, a_n]\), you need to determine the maximum sum of a subarray \(A[i \dots j]\) for \(1 \leq i \leq j \leq n\). This can be formulated as:

\[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \]

The problem can be solved efficiently using Kadane's algorithm with a time complexity of \(O(n)\).

inputFormat

The first line of input contains an integer n (the number of elements in the array). The second line contains n space-separated integers, representing the elements of the array.

outputFormat

Output a single integer representing the largest sum of any non-empty subarray.

## sample

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

6

</p>