Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. A subarray is defined as a contiguous segment of the array and must contain at least one element. Formally, if the array is \(a_1, a_2, \ldots, a_n\), you need to compute \(\max_{1 \le i \le j \le n} \sum_{k=i}^j a_k\).

This problem is a classic algorithmic challenge that can be solved efficiently using Kadane's algorithm.

inputFormat

The first line of input contains an 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 sum of any contiguous subarray.

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

6