DSA interview question

Print the Subarray with the Maximum Sum

Medium · Algorithms · Topics: array, dynamic programming, kadane's

The problem

The stock analyst from the Kadane's problem is happy with the best total, but the report also has to say which days made up that best stretch: the start date and the end date. That means extending Kadane's algorithm to remember where the current run began and where the best run begins and ends. If several subarrays share the maximum sum, the report shows the one found first (the earliest start).

Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → sum 6, subarray [4, -1, 2, 1] (indices 3 to 6).

Function signature

struct Best { long long sum; int start, end; };
Best maxSubarrayWithRange(const vector<int>& a);  // a is non-empty; inclusive indices

Test cases

Input `a`	Output	Explanation
`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`	sum 6, `[4, -1, 2, 1]` (3..6)
`[5, 4, -1, 7, 8]`	sum 23, whole array (0..4)
`[-3, -1, -2]`	sum -1, `[-1]` (1..1)	All negative
`[1]`	sum 1, `[1]` (0..0)
`[2, -1, 2, -10, 3]`	sum 3, `[2, -1, 2]` (0..2)	`[3]` also sums to 3, but the earlier one is kept

(Confirm: the subarray is non-empty; on ties, report the first maximum found.)

How interviewers phrase it

"Find the maximum subarray sum and print the subarray."
A direct follow-up to Kadane's algorithm: "Now also return the start and end indices."

Clarifying questions to ask

Which subarray should be returned if several have the same maximum sum?
Indices or the elements themselves?
Is the array non-empty?

Follow-ups to expect

"Which extra variables do you need?"
"When does the current start move?"
"How do you prefer the earliest subarray on ties?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview