Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum, and then return its sum. A subarray is defined as a sequence of consecutive elements in the array. This is a classic problem that can be solved efficiently using Kadane's algorithm. The mathematical formulation of the problem is as follows:

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

Read the input from stdin and output the result to stdout.

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing 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 which is the maximum sum of any contiguous subarray.

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

6