DSA interview question

Maximum Subarray Sum (Kadane's Algorithm)

Medium · Algorithms · Topics: array, dynamic programming, greedy

The problem

A stock analyst has the daily price changes for a year (some days up, some down) and wants the best stretch of consecutive days to have held the stock, meaning the contiguous subarray with the largest total. Trying every start and end is O(n²). Kadane's algorithm scans once, keeping the best sum of a subarray ending at the current day: either extend yesterday's best run, or start fresh today if yesterday's run was dragging the total down.

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

Function signature

long long maxSubArray(const vector<int>& nums);  // largest sum of a non-empty contiguous subarray

Test cases

Input `nums`	Output	Explanation
`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`	6	`[4, -1, 2, 1]`
`[1]`	1
`[5, 4, -1, 7, 8]`	23	The whole array
`[-3, -1, -2]`	-1	All negative: the best is the single largest element
`[0, -1, 0]`	0

(Confirm: the subarray must be non-empty, so an all-negative array returns its largest element, not 0.)

How interviewers phrase it

"Find the contiguous subarray with the largest sum" (LeetCode 53).
"Return the subarray itself" (S.No 80).
Variants: maximum circular subarray sum, maximum product subarray (S.No 101).

Clarifying questions to ask

Must the subarray be non-empty? (Decides the all-negative case.)
Return the sum, or the start and end indices?
How large can the values be? (Use 64-bit sums.)

Follow-ups to expect

"What's the recurrence?"
"Why reset when the running sum goes negative?"
"What about an all-negative array?"
"How do you recover the subarray?"
"Is there a divide-and-conquer solution?"
"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