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. This is a classic problem that is most effectively solved using Kadane's Algorithm. In mathematical terms, you are required to compute:

where (a_k) denotes the elements of the array.

Input consists of an integer n followed by n space-separated integers. Output the maximum subarray sum.

inputFormat

The first line of input contains a single integer n ((1 \leq n \leq 10^5)), representing the number of elements in the array. The second line contains n space-separated integers, each representing an element of the array. The absolute value of each element will be within reasonable limits.

outputFormat

Output a single integer: the maximum sum of any contiguous subarray within the given array.## sample

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

6