Maximum Sum Subarray

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray within the given array. This problem is a classic example where Kadane's Algorithm is applied to efficiently determine the answer in O(n) time.

The maximum sum subarray is defined as:

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

If the input array is empty, the result should be 0.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers.

If n is 0, the array is considered empty.

outputFormat

Output the maximum sum of any contiguous subarray. The result is printed to standard output (stdout).

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

6