Maximum Subarray Sum with Indices

You are given an array of integers. Your task is to find the contiguous subarray (of size \( \geq 1 \)) within the array that has the maximum sum, and output this sum along with the starting and ending indices of this subarray.

If the array is empty, output \(0\) for the maximum sum and \(-1\) for both indices.

This problem can be solved efficiently using Kadane's algorithm. In particular, let \(a_i\) be the elements of the array. You need to find indices \(l\) and \(r\) such that the sum \(\sum_{i=l}^{r} a_i\) is maximized.

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. If \(n = 0\), then the array is empty.

outputFormat

Output to stdout three space-separated integers: the maximum sum, the starting index, and the ending index of the contiguous subarray that produces this maximum sum.

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

6 3 6