Kadane's Algorithm and Maximum Subarray Variants: An Interview Walkthrough

"Find the contiguous subarray with the largest sum" is one of the most common array questions in coding interviews. The brute-force approach checks every subarray in O(n^2) or worse. Kadane's algorithm solves it in O(n) time and O(1) space, and the same idea unlocks a family of follow-up questions interviewers love to ask. THE CORE INSIGHT At each index, the best subarray ending here is either: - the current element alone, or - the current element added to the best subarray ending at the previous index. If the running sum has become negative, it can only hurt what comes next, so you drop it and start fresh. def max_subarray(nums): best = cur = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return best Initialize with nums[0], not 0. Otherwise an all-negative array like [-3, -1, -2] incorrectly returns 0 instead of -1. Interviewers often test this edge case directly. EXPLAINING WHY IT WORKS Frame it as dynamic programming: dp[i] = max(nums[i], dp[i-1] + nums[i]), and the answer is the maximum dp value. Because each state depends only on the previous one, you compress the array into a single variable. Saying this out loud shows you understand the algorithm instead of just memorizing it. RETURNING THE INDICES A common follow-up asks for the subarray itself. Track where the current run starts: def max_subarray_range(nums): best, cur = nums[0], nums[0] start = best_l = best_r = 0 for i in range(1, len(nums)): if nums[i] > cur + nums[i]: cur, start = nums[i], i else: cur += nums[i] if cur > best: best, best_l, best_r = cur, start, i return best, best_l, best_r VARIANTS TO PREPARE 1. Maximum product subarray. Negative numbers flip signs, so track both the maximum and minimum product ending at each index, and swap them when you see a negative value. 2. Maximum circular subarray sum. The answer is either the normal Kadane result, or the total sum minus the minimum subarray sum (the wrap-around case). If every number is negative, return the normal result, since "total minus minimum" would mean an empty subarray. 3. Best time to buy and sell stock. Convert prices to daily differences and the problem becomes a maximum subarray, or simply track the minimum price seen so far. 4. Maximum sum rectangle in a 2D matrix. Fix a pair of top and bottom rows, collapse columns into a 1D array of sums, and run Kadane on it. That gives O(rows^2 * cols). 5. Maximum subarray with at most one deletion. Keep two states: best sum ending here with no deletion, and best sum ending here with one deletion used. COMPLEXITY TALKING POINTS - Time: O(n), one pass. - Space: O(1) for the base version. - For the 2D version, mention the trade-off of choosing the smaller dimension for the outer loops. HOW TO PRESENT IT Start with brute force, mention prefix sums as an O(n^2) improvement, then introduce Kadane as the O(n) solution with the "drop a negative running sum" intuition. Test it aloud on [-2, 1, -3, 4, -1, 2, 1, -5, 4], which should return 6 for [4, -1, 2, 1]. Staying clear and structured under time pressure is the real challenge. Some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their explanation on track. Master the base pattern and its variants, and maximum subarray questions become reliable points in any coding round.