Maximum Sum Contiguous Subarray

You are given an array of integers. Your task is to find the maximum sum of a contiguous subarray. In other words, you need to choose a segment of consecutive elements (possibly the whole array) such that their sum is maximized.

If the array is empty, output 0. In case the array consists of all negative numbers, the answer is the maximum (i.e. least negative) element.

This is a classic problem that is typically solved using Kadane's Algorithm. The solution must read input from standard input (stdin) and output the answer to standard output (stdout).

The mathematical formulation of the problem is as follows:

Given an array \(a_1, a_2, \cdots, a_n\), compute \[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \] with the convention that the maximum sum for an empty array is \(0\).

inputFormat

The first line of input contains a single integer n (\(0 \leq n \leq 10^5\)) which denotes the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer — the maximum sum of any contiguous subarray of the given array. If the array is empty, output 0.

6
1 2 -3 4 -2 1

4