Maximum Subarray Sum Problem

You are given an integer array. Your task is to find a contiguous subarray which has the largest sum and then output both the maximum sum and the subarray itself.

If the array is empty, output 0 as the maximum sum and leave the subarray empty.

Note: If there are multiple subarrays with the same maximum sum, you may print any one of them.

Hint: You might want to consider using Kadane's algorithm.

inputFormat

The first line contains a single integer n representing the number of elements in the array. If n is 0, the array is empty.

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

outputFormat

Output two lines:

• The first line contains the maximum subarray sum.
• The second line contains the contiguous subarray with the maximum sum, with elements separated by a space. If the subarray is empty, this line should be empty.

If the answer is computed using a formula, note that the recurrence relation for Kadane's algorithm can be written in LaTeX as:

\( dp[i] = \max( arr[i], dp[i-1] + arr[i] ) \)

## sample

5
1 -3 2 1 -1

3
2 1

</p>