Maximum subarray sum start and end indices
Filed under Adobe
Free read 3 of 3Confirm index numbering and behavior when all numbers are negative.
The question
Given an integer array containing both positive and negative values, find the start and end indices of the contiguous subarray that has the maximum sum.
Constraints
- Array contains at least one element
- If multiple subarrays have the same maximum sum, return any valid pair of start and end indices
Examples
- Input
- nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output
- start = 3, end = 6
- Why
- The subarray [4, -1, 2, 1] has the largest sum = 6.
Approach
Confirm index numbering and behavior when all numbers are negative.
Check every possible start and end index combination, calculating the sum for each subarray in O(N^2) or O(N^3) time.
Use Kadane's Algorithm. Maintain current sum and max sum, while recording potential start index updates whenever current sum drops below zero and resets.
Array with a single element or arrays where maximum sum is achieved by a single negative number.
Solution
O(n) time, O(1) space
class Solution:
def maxSubArrayIndices(self, nums: list[int]) -> tuple[int, int]:
max_sum = curr_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr_sum + nums[i]:
curr_sum = nums[i]
temp_start = i
else:
curr_sum += nums[i]
if curr_sum > max_sum:
max_sum = curr_sum
start = temp_start
end = i
return (start, end)
Tips
- What they are testing: Test with all negative numbers, all positive numbers, and single-element arrays.
- Common mistake: Returning only the max sum value instead of tracking the start and end index boundaries correctly.
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.