Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum sum over all contiguous subarrays. That is, given an array \(a_1, a_2, \dots, a_n\), find the value of

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

If the array is empty, the answer is defined as 0. This problem is a classic application of Kadane's algorithm.

inputFormat

The input is read from stdin and has the following format:

• 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 elements of the array.

outputFormat

Output the maximum sum of a contiguous subarray to stdout. If the array is empty (n = 0), output 0.

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

6