Maximum Contiguous Subarray

You are given an array of integers and your task is to find the contiguous subarray that has the maximum sum. This subarray should be as long as possible if there exist multiple subarrays with the same maximum sum.

Implement the solution using Kadane's Algorithm which operates in O(n) time. The key recurrence used in Kadane's Algorithm is given in the following \( \text{formula} \):

\[ \text{currentSum} = \max(\text{nums}[i],\; \text{currentSum} + \text{nums}[i]) \]

Take care of the edge case when the input array is empty.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \( n \) which denotes the number of elements in the array. The second line contains \( n \) space-separated integers. If \( n = 0 \), the array is empty.

outputFormat

Output the contiguous subarray with the maximum sum. The result should be printed to standard output (stdout) as a sequence of numbers separated by a single space. For an empty array, output nothing.

## sample

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

4 -1 2 1

</p>