Longest Maximum Sum Contiguous Subarray

You are given an array of integers. The task is to find a contiguous subarray such that its sum is maximized. In case there exist multiple subarrays with the same maximum sum, choose the one with the greatest length. If there are still multiple candidates, return the subarray that appears first.

The solution must have an average time complexity of \(O(n)\). For example:

• For input [1, -2, 3, 4, -5, 3, 4, -6], the maximum sum subarray is [3, 4, -5, 3, 4].
• For input [1, 2, -1, 1, 2, -1, 1, 2], the entire array is the answer.
• For an all-negative array such as [-1, -2, -3, -4, -5], the answer is [-1].

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

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a single integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

Note: \(0 \leq n \leq 10^5\).

outputFormat

Output the contiguous subarray with the maximum sum. The elements should be printed in order on a single line, separated by spaces. If the array is empty, output an empty line.

1
1

1