Maximum Subarray Sum

Problem Description

You are given an array of n integers. Your task is to find the maximum sum of any contiguous subarray. In other words, if the array is represented as \(a_1, a_2, \ldots, a_n\), you need to find the maximum value of \(\sum_{i=l}^{r} a_i\) for \(1 \leq l \leq r \leq n\).

You can solve this problem efficiently with Kadane's Algorithm, which works in \(O(n)\) time by iteratively updating the current subarray sum and maintaining the maximum found so far.

Please note that the input will be provided in the standard input (stdin) and the answer must be printed to the standard output (stdout).

inputFormat

Input Format

The input consists of two lines:

1. The first line contains an integer \(n\), which represents the number of elements in the array.
2. The second line contains \(n\) space-separated integers, representing the elements of the array.

outputFormat

Output Format

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

## sample

5
1 -2 3 4 -1

7