Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output its sum. In other words, for an array \(A\) of size \(n\), you need to compute:

\(\max_{1 \le i \le j \le n} \sum_{k=i}^{j} A_k\)

This is a classic problem that can be solved efficiently using Kadane's Algorithm with a time complexity of \(O(n)\). Make sure your solution reads input from stdin and writes the result to stdout.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) representing 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 which is the maximum sum obtainable by any contiguous subarray of the given array.

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

6