Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum possible sum of a contiguous subarray. This is a classical problem that can be solved efficiently using Kadane's Algorithm.

The solution involves iterating through the array and at each step, deciding whether to extend the previous subarray or start a new one. The answer is the largest sum encountered during this process.

The mathematical formulation of the problem is as follows: Let \(a_1, a_2, \dots, a_n\) be the given sequence, you need to compute \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\).

inputFormat

The input is read from standard input (stdin) and follows the format below:

The first line contains a single integer n (1 ≤ n ≤ 105), the number of elements in the array.
The second line contains n space-separated integers, each representing an element of the array. Each integer is between -109 and 109 inclusive.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray. The output should be written to standard output (stdout).

1
5

5