Maximum Subarray Sum

You are given an integer array a consisting of n elements. Your task is to find the sum of the contiguous subarray within a which has the largest sum.

Formally, you need to compute the maximum value of the sum $$ S(i,j)=\sum_{k=i}^{j} a_k, \quad 1 \leq i \leq j \leq n, $$ with the special case that for an empty array the answer is defined as 0.

This is a classic problem that can be effectively solved using Kadane's algorithm.

inputFormat

The input is given from stdin and is formatted as follows:

• The first line contains an integer n — 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 to stdout: the maximum subarray sum.

3
5 -3 5

7