Maximum Subarray Sum

Given an array of integers representing daily sales figures, your task is to determine the maximum sum that can be obtained by summing a contiguous segment of the array. Formally, for an array (a = [a_1, a_2, \dots, a_n]), you are to compute

[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k ]

This is a classic problem that can be efficiently solved by Kadane's algorithm.

inputFormat

The first line of input contains a positive integer (n), the number of elements in the array. The second line contains (n) space-separated integers which may be positive, negative, or zero.

outputFormat

Print a single integer representing the maximum sum of any contiguous subarray of the given array.## sample

1
1

1