Maximum Subarray

Given an array of integers, find the contiguous subarray which has the maximum sum. In other words, if the array is \(a_1,a_2,\dots,a_n\), you need to find indices \(l\) and \(r\) such that the sum

[ S = \sum_{i=l}^{r} a_i ]

is maximized. If there are multiple subarrays achieving the same maximum sum, return the one that appears first in the array. If the array is empty, output nothing.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output the contiguous subarray with the maximum sum to stdout as a sequence of space-separated integers. If the input array is empty (i.e. \(n=0\)), output nothing.

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

4 -1 2 1