Maximum Sum Contiguous Subarray | Dataford Interview Questions

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.

Constraints

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

Function Signature

def max_subarray(nums):

Your question is Maximum Sum Contiguous Subarray. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem