Maximum Contiguous Subsequence Sum

You are given an array of integers. Your task is to compute the maximum sum of any contiguous subsequence (subarray) of the array. In other words, if the array is \(a_1, a_2, \dots, a_n\), you must find \[ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k \] This problem is a classic application of Kadane's algorithm.

The input is provided via standard input (stdin) and the output should be produced on standard output (stdout).

inputFormat

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

Example:

5
1 -2 3 4 -5

outputFormat

Output a single integer: the maximum sum of any contiguous subarray of the given array.

Example Output:

7

5
1 -2 3 4 -5

7