Maximum Subarray Sum

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 this sum. This problem can be efficiently solved using Kadane's Algorithm. The algorithm follows the recurrence relation:
$current = \max(a_i, current + a_i)$ and $global = \max(global, current)$,
where $a_i$ is the current element.

Use this method to consider every possible subarray in a single pass through the array.

inputFormat

The input starts with an integer n on the first line representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer representing the maximum sum of any contiguous subarray.## sample

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

6