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.
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]List[int]
max_sum: maximum sum over all contiguous subarraysstart_index: starting index of one maximum-sum subarrayend_index: ending index of that subarrayIf multiple subarrays have the same maximum sum, returning any one of them is acceptable.
Example 1
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4][6, 3, 6][4, -1, 2, 1] has sum 6, which is the largest possible.Example 2
nums = [1][1, 0, 0][1].1 <= len(nums) <= 10^5-10^4 <= nums[i] <= 10^4nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output[6, 3, 6]WhyThe subarray from index 3 to 6 is `[4, -1, 2, 1]`, and its sum is 6.nums = [1]Output[1, 0, 0]WhyThere is only one possible contiguous subarray, so it is the answer.nums = [-5, -2, -8]Output[-2, 1, 1]WhyWhen all numbers are negative, the best subarray is the single largest element.1 <= len(nums) <= 10^5-10^4 <= nums[i] <= 10^4The input array is non-emptyThe chosen subarray must be contiguousdef max_subarray(nums):
