Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum sum of a contiguous subarray. In other words, if the array is denoted as \(a_1, a_2, \dots, a_n\), compute:

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

This is a classic problem that can be efficiently solved using Kadane's algorithm with a time complexity of \(O(n)\). Be sure to consider cases where all numbers are negative.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) indicating the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer which is the maximum sum that can be obtained from any contiguous subarray of the given array.

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

6