Maximum Subarray Sum

You are given an array of integers \(a_1,a_2,\ldots,a_n\) and your task is to find the maximum sum of any contiguous subarray. In other words, you need to compute

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

If the input array is empty, return 0. This problem can be efficiently solved using Kadane's algorithm, which works in \(O(n)\) time complexity.

Example: For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6.

inputFormat

The input is read from standard input (stdin) and consists of two parts:

1. The first line contains an integer \(n\), representing the number of elements in the array.
2. If \(n > 0\), the second line contains \(n\) space-separated integers. If \(n = 0\), the array is considered empty.

outputFormat

Output a single integer to standard output (stdout) --- the maximum sum of any contiguous subarray. If the array is empty, output 0.

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

6