Maximum Subarray Sum

Given an array of integers, your task is to find the sum of the contiguous subarray (containing at least one number) which has the largest sum. This problem is a classic example often solved using Kadane's algorithm.

More formally, given an array \(A = [a_1,a_2,\dots,a_n]\), find a contiguous subarray \(A[i \dots j]\) such that its sum \(S = \sum_{k=i}^{j} a_k\) is maximized. The answer must be output as a single integer.

inputFormat

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

outputFormat

Output a single integer which is the sum of the subarray with the maximum sum.

4
2 3 1 5

11