Maximum Subarray Sum

Given an array of integers, find the sum of the contiguous subarray (containing at least one number) which has the largest sum. This is a classic problem that can be optimally solved using Kadane's algorithm. More formally, given an array \( A = [a_1, a_2, \dots, a_N] \), you need to compute \( \max_{1 \leq i \leq j \leq N} \sum_{k=i}^{j} a_k \). For example, if the array is [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6.

inputFormat

The first line contains an integer \( N \) denoting 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 which is the largest sum of a contiguous subarray.

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

6