Maximum Subarray Sum

You are given a sequence of integers. Your task is to find the sum of the contiguous subarray with the largest sum. This is a classic problem that can be solved efficiently using Kadane's algorithm.

Formally, given an array \( A = [a_1, a_2, \dots, a_n] \), find the maximum value of the sum of a subarray, i.e., find \( \max_{1 \leq i \leq j \leq n} \left( \sum_{k=i}^{j} a_k \right) \). In the case of an empty array, the answer is defined to be 0.

Example: For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with the largest sum is [4, -1, 2, 1] and the sum is 6.

inputFormat

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

• The first line contains a single integer \( n \) indicating the number of elements in the array. \( n \) can be zero.
• If \( n > 0 \), the second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

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

0

0