Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

This problem can be solved efficiently using Kadane's Algorithm. The key idea is to use dynamic programming where at each position you decide whether to start a new subarray or to extend the current subarray.

In mathematical terms, given an array \(a_1, a_2, \dots, a_n\), we want to compute:

\[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \]

inputFormat

The first line contains a single integer \(n\) representing 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 subarray sum.

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

6