Maximum Contiguous Subarray Sum

You are given a sequence of integers. Your task is to find the maximum sum of a contiguous subsequence of the sequence.

Note: The contiguous subsequence must contain at least one number.

This is a classical problem known as the Maximum Subarray Problem or Kadane's Algorithm. The optimal solution uses a dynamic programming approach with a time complexity of O(n).

For example, given the input:

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

the maximum contiguous sum is 6 (from the subsequence [4, -1, 2, 1]).

In some cases with all negative numbers, the answer is the largest (least negative) number.

The mathematical formulation for updating the current best sum is given by the recurrence:

$$max\_current = \max(a_i, max\_current + a_i)\quad \text{for } i \ge 2, $$

with initial condition

$$max\_current = max\_global = a_1.$$

inputFormat

The input is read from stdin and consists of a single line containing space-separated integers. These integers represent the sequence from which you must find the maximum contiguous subarray sum.

Constraints:

• The sequence will contain at least one integer.
• Each integer can be positive, negative, or zero.

outputFormat

Output the maximum contiguous subarray sum on stdout as a single integer.

## sample

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

6