Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and output its sum. This problem can be formally defined as follows: Given an array \(A\) of length \(n\), find indices \(i\) and \(j\) such that \(1 \le i \le j \le n\) and the sum \(\sum_{k=i}^{j} A[k]\) is maximized.

Note: The subarray must contain at least one element.

inputFormat

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

outputFormat

Output a single integer, the largest sum of any contiguous subarray of the given array.

9
-2 1 -3 4 -1 2 1 -5 4

6