Maximum Subarray

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output that sum.

You are required to compute the value:

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

This is a classic problem and can be efficiently solved by using Kadane's algorithm.

inputFormat

The input is given from stdin and consists of two lines:

• The first line contains an integer \( n \) which represents the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Print to stdout a single integer which is the maximum sum of any contiguous subarray.

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

6