Maximum Sum Contiguous Subarray

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. Formally, given a sequence \(a_1, a_2, \ldots, a_n\), you need to compute:

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

If the array is empty or if every number is negative, then the answer is defined to be 0.

This problem is a classic application of Kadane's algorithm.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(n \geq 0\)) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers. If \(n = 0\), the array is considered empty.

outputFormat

Output a single integer which is the maximum sum of a contiguous subarray.

## sample

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

6

</p>