Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray that has the maximum sum and report the sum along with its starting and ending indices (1-indexed). This problem can be solved efficiently using Kadane's algorithm. In mathematical terms, you are required to compute $$\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j}a_k,$$ where \(a_k\) represents the element at the \(k\)-th position of the array.

If there are multiple subarrays with the same maximum sum, output the one that appears first.

inputFormat

The input consists of two lines. The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output three space-separated integers: the maximum subarray sum, the starting index, and the ending index. The indices are 1-based.## sample

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

6 4 7