Maximum Subarray Sum

You are given an integer n and an array of n integers. Your task is to compute the maximum possible sum of a contiguous subarray.

This problem is a classic application of Kadane's Algorithm. Formally, given an array \( a_1, a_2, \ldots, a_n \), you need to find:

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

Note that the subarray must contain at least one element.

inputFormat

The input is given via standard input and consists of two lines:

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

outputFormat

Output a single integer via standard output: the maximum sum of any contiguous subarray in the given array.

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

6