Maximum Subarray Sum

Given an array of integers that represent the distances Alice ran over some days, your task is to find the contiguous subarray (containing at least one element) that has the largest sum and return its sum.

You can solve this problem using Kadane's Algorithm with a time complexity of \(O(n)\). The sum of a subarray from index \(l\) to \(r\) is defined as \(\sum_{i=l}^{r}\, distances[i]\).

inputFormat

The first line of input contains an integer \(n\) representing the number of days. If \(n > 0\), the second line contains \(n\) space-separated integers representing the distances run on each day. If \(n\) is 0, then no second line is provided.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray.

5
1 -2 3 4 -1

7