Maximum Subarray Sum

Given a sequence of integers, your task is to compute the maximum sum obtainable by summing a contiguous subarray of the sequence. This is a classic problem that is often solved using Kadane's algorithm. The algorithm iterates through the array while keeping track of the maximum subarray sum possible at each index.

Mathematical Formulation:

Let \(a_1, a_2, \dots, a_n\) be the sequence of integers. You need to find the maximum value of \(S(i,j)=\sum_{k=i}^{j} a_k\) for \(1 \le i \le j \le n\).

Example:

Input: -2 1 -3 4 -1 2 1 -5 4
Output: 6

inputFormat

The input consists of a single line containing space-separated integers representing the array.

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray from the given list.

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

6