Maximum Subarray Sum

Given an array of integers \( nums \) with length \( n \) (where \( 1 \leq n \leq 10^4 \) and \( -10^5 \leq nums[i] \leq 10^5 \)), your task is to find the contiguous subarray (containing at least one number) which has the maximum sum and output that sum.

Hint: This problem can be efficiently solved using Kadane's algorithm which runs in \( O(n) \) time.

For example, given the input array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with maximum sum is [4, -1, 2, 1] and its sum is 6.

inputFormat

The input is given via standard input (stdin) in the following format:

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 representing the maximum sum of any contiguous subarray. The output should be written to standard output (stdout).

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

6