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 output its sum. This problem can be solved efficiently using Kadane's algorithm with a time complexity of \(O(n)\).

The solution must read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line contains an integer \(n\) (\(n \geq 1\)) representing the number of elements in the array. The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

Output a single integer representing the maximum subarray sum.

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

6