Maximum Subarray Sum

Given an integer array, your task is to find the largest sum of any contiguous subarray.

Mathematically, for an array \(a_1, a_2, \dots, a_n\), you are required to compute:

\(\max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k\)

This is a classic problem which can be solved efficiently with Kadane's algorithm. Read the input from stdin and output the result to stdout.

inputFormat

The first line contains a single integer N representing the number of elements in the array. The second line contains N space-separated integers.

outputFormat

Output a single integer which is the maximum subarray sum.

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

6