Maximum Subarray Sum

You are given an integer array of length n. Your task is to find the maximum sum of any contiguous subarray. This is a classic problem that can be effectively solved using Kadane's algorithm.

Constraints:

• 1 ≤ n ≤ 10⁶
• -10⁹ ≤ each array element ≤ 10⁹

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

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray.

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

6