Maximum Subarray Sum

Given an array of integers, your task is to find the largest sum of any contiguous subarray. The problem can be solved efficiently using Kadane's algorithm. The maximum subarray sum is defined as: $$max_sum = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k.$$

inputFormat

The input consists of two lines. The first line contains an integer $$n$$ ($$1 \leq n \leq 10^5$$), which is the number of elements in the array. The second line contains $$n$$ space-separated integers representing the elements of the array.

outputFormat

Output a single integer that is the largest sum of a contiguous subarray.## sample

1
1

1