Problem

On a Meta surface such as Facebook Feed analytics, you are given an integer array representing per-minute engagement deltas. Find the contiguous subarray with the largest possible sum, and return that sum along with the start and end indices of one optimal subarray.

Formal Specification

Implement a function that takes a non-empty list of integers nums and returns a list [max_sum, start_index, end_index].

• nums: List[int]
• Return: List[int]
  • max_sum: maximum sum over all contiguous subarrays
  • start_index: starting index of one maximum-sum subarray
  • end_index: ending index of that subarray

If multiple subarrays have the same maximum sum, returning any one of them is acceptable.

Examples

Example 1

• Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• Output: [6, 3, 6]
• Explanation: The subarray [4, -1, 2, 1] has sum 6, which is the largest possible.

Example 2

• Input: nums = [1]
• Output: [1, 0, 0]
• Explanation: The only subarray is [1].

Constraints

• 1 <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4
• The input array is non-empty.
• The subarray must be contiguous.