Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum sum of any contiguous subarray. In mathematical form, you need to find

$$\max_{1 \leq i \leq j \leq n}\left(\sum_{k=i}^{j} a_k\right)$$

The array might contain negative numbers. The solution should work in O(n) time complexity.

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 array elements.

outputFormat

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

5
1 2 3 4 5

15