Maximum Subarray Sum

The problem is to compute the maximum sum of any contiguous subarray from a given list of integers. This is a classic problem which can be efficiently solved using Kadane's algorithm. The algorithm maintains a running sum and updates the maximum sum found so far. It is particularly useful for handling arrays containing both positive and negative integers.

inputFormat

The input consists of multiple space-separated integers read from standard input. The first integer is n (the number of elements in the array), followed by n integers representing the array elements. For example:
9\n-2 1 -3 4 -1 2 1 -5 4

outputFormat

Output the maximum sum of a contiguous subarray computed from the provided array. The result should be printed to standard output.

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

6