Maximum Sum Subarray with Shortest Length

Given an array of integers, find the contiguous subarray which has the maximum sum. If there are multiple subarrays with the maximum sum, output the one with the minimal length.

More formally, let \(A = [a_1, a_2, \dots, a_n]\). You are to find indices \(l\) and \(r\) such that the sum \(S = \sum_{i=l}^{r} a_i\) is maximized. In the case of ties (i.e. multiple \(l, r\) pairs yield the same maximum sum), choose the subarray with the smallest length \(r-l+1\>.

If the input array is empty, output an empty line.

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

If \(n = 0\), the second line may be omitted.

outputFormat

Print the contiguous subarray (i.e. the elements separated by a single space) that has the maximum sum. In case multiple subarrays have the same maximum sum, print the one with the shortest length. If the array is empty, print an empty line.

5
1 -3 2 1 -1

2 1