Maximum Subarray Sum

Given an array of integers, find the subarray (contiguous part of the array) with the maximum sum. This is a classic problem that can be solved with Kadane's algorithm efficiently.

Formally, you are given an array \(a_1, a_2, \ldots, a_n\). You need to find the maximum value of \(\sum_{k=i}^{j} a_k\) for any \(1 \le i \le j \le n\). In other words:

\(\text{max_subarray_sum}(a) = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\)

inputFormat

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

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray.## sample

1
1

1