Kadane algorithm interview questions with worked solutions
Last updated 2026-11-19
Kadane's algorithm finds the contiguous subarray with the largest sum in a single pass. The idea is a running decision at each element: either extend the best subarray ending at the previous position or start fresh here. Whichever is larger becomes the best subarray ending here, and the overall answer is the best of those.
The algorithm is a tiny dynamic program, with O(1) memory. This page starts with the core problem and then works through the variants that interviewers use to test whether you understand the recurrence: tracking indices, circular arrays, products, one deletion, absolute sums, a length constraint and a 2D matrix. See dynamic programming questions for the wider family and arrays questions for related single-pass problems.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Recurrence | best_here = max(a[i], best_here + a[i]) |
The recurrence
Let best_here be the maximum sum of a subarray ending at index i. Then best_here = max(a[i], best_here + a[i]). A negative running sum is never worth carrying, because starting at a[i] alone is better. The answer is the maximum best_here over all i.
Initialise with the first element, not zero, unless the problem allows an empty subarray. Starting at zero silently turns an all-negative array into an answer of 0, which is wrong when at least one element is required.
- Maximum sum: extend or restart.
- Minimum sum: the same with min.
- Circular: total minus the minimum subarray, unless every element is negative.
- Product: track both the maximum and the minimum because a negative flips them.
When Kadane does not apply
A length constraint (at least k elements) or a requirement of a sum limit breaks the simple recurrence. Use prefix sums with a running minimum for the first, and see prefix sum questions for the second.
Kadane algorithm interview questions with worked solutions: questions with worked answers
1 Maximum subarray sum (at least one element).
easyKeep the best sum of a subarray ending at the current element and the best overall. For each element, the running sum is the larger of the element alone or the previous running sum plus the element. For [-2,1,-3,4,-1,2,1,-5,4] the answer is 6 from [4,-1,2,1]. Time O(n), space O(1).. Edge cases: all negative values (the answer is the largest single element), one element, zeroes.
pythondef max_subarray(a): cur = best = a[0] for x in a[1:]: cur = max(x, cur + x) best = max(best, cur) return bestjavaimport java.util.*; class Solution { static int maxSubArray(int[] a) { int cur = a[0], best = a[0]; for (int i = 1; i < a.length; i++) { cur = Math.max(a[i], cur + a[i]); best = Math.max(best, cur); } return best; } }2 Return the maximum subarray together with its start and end indices.
easyTrack where the current run began. When the running sum before this element is negative, restart the run at the current index; otherwise extend it. Whenever the running sum exceeds the best, record the start and end. Restarting only when the sum is strictly negative keeps the longer subarray when a zero sum is possible. Time O(n), space O(1).. Edge cases: all negative values (single element), ties between equal sums, one element.
pythondef max_subarray_range(a): best = cur = a[0] s = bs = be = 0 for i in range(1, len(a)): if cur < 0: cur, s = a[i], i else: cur += a[i] if cur > best: best, bs, be = cur, s, i return best, bs, bejavaimport java.util.*; class Solution { static int[] maxSubArrayRange(int[] a) { int best = a[0], cur = a[0], s = 0, bs = 0, be = 0; for (int i = 1; i < a.length; i++) { if (cur < 0) { cur = a[i]; s = i; } else cur += a[i]; if (cur > best) { best = cur; bs = s; be = i; } } return new int[]{best, bs, be}; } }3 Best time to buy and sell stock once, seen as Kadane on price differences.
easyThe profit of buying on day i and selling on day j is the sum of the daily differences between them, which is a subarray sum of the difference array. So the best single transaction is the maximum subarray sum of the differences, with the empty subarray (0) allowed. The running sum is floored at 0 to model "do not buy yet". Time O(n), space O(1).. Edge cases: prices only falling (0), one price, flat prices.
pythondef max_profit(prices): cur = best = 0 for i in range(1, len(prices)): cur = max(0, cur + prices[i] - prices[i - 1]) best = max(best, cur) return bestjavaimport java.util.*; class Solution { static int maxProfit(int[] p) { int cur = 0, best = 0; for (int i = 1; i < p.length; i++) { cur = Math.max(0, cur + p[i] - p[i - 1]); best = Math.max(best, cur); } return best; } }4 Maximum absolute sum of any subarray (an empty subarray counts as 0).
mediumThe largest absolute value is either the largest positive subarray sum or the most negative one. Run the maximum version and the minimum version of Kadane together, flooring the running maximum at 0 and capping the running minimum at 0. The answer is the larger of the best maximum and the negated best minimum. Time O(n), space O(1).. Edge cases: all negative values, all positive values, mixed signs.
pythondef max_absolute_sum(a): cmax = cmin = best = 0 for x in a: cmax = max(0, cmax + x) cmin = min(0, cmin + x) best = max(best, cmax, -cmin) return bestjavaimport java.util.*; class Solution { static int maxAbsoluteSum(int[] a) { int cmax = 0, cmin = 0, best = 0; for (int x : a) { cmax = Math.max(0, cmax + x); cmin = Math.min(0, cmin + x); best = Math.max(best, Math.max(cmax, -cmin)); } return best; } }5 Maximum sum circular subarray: the subarray may wrap around the end.
mediumA wrapping subarray is the whole array minus a non-wrapping subarray in the middle, so its sum is total minus the minimum subarray sum. The answer is the larger of the ordinary Kadane maximum and total minus the Kadane minimum. If every element is negative, total minus the minimum is 0 (an empty selection), which is not allowed, so return the ordinary maximum. Time O(n), space O(1).. Edge cases: all negative values (ordinary maximum), all positive values (the whole array), one element.
pythondef max_subarray_circular(a): total = 0 cmax = cmin = 0 best, worst = a[0], a[0] for x in a: cmax = max(x, cmax + x) cmin = min(x, cmin + x) best = max(best, cmax) worst = min(worst, cmin) total += x return best if best < 0 else max(best, total - worst)javaimport java.util.*; class Solution { static int maxSubarrayCircular(int[] a) { int total = 0, cmax = 0, cmin = 0, best = a[0], worst = a[0]; for (int x : a) { cmax = Math.max(x, cmax + x); cmin = Math.min(x, cmin + x); best = Math.max(best, cmax); worst = Math.min(worst, cmin); total += x; } return best < 0 ? best : Math.max(best, total - worst); } }6 Maximum product subarray.
mediumA negative number can turn the smallest product into the largest, so track both the maximum and minimum product of a subarray ending at the current element. For each x, the candidates are x itself, max * x and min * x. Update both from the same set of three. A zero resets both naturally because every candidate becomes 0 or x. Time O(n), space O(1).. Edge cases: zeroes splitting the array, an even or odd count of negatives, one element.
pythondef max_product(a): cmax = cmin = best = a[0] for x in a[1:]: c = (x, cmax * x, cmin * x) cmax, cmin = max(c), min(c) best = max(best, cmax) return bestjavaimport java.util.*; class Solution { static int maxProduct(int[] a) { int cmax = a[0], cmin = a[0], best = a[0]; for (int i = 1; i < a.length; i++) { int x = a[i]; int p = cmax * x, q = cmin * x; cmax = Math.max(x, Math.max(p, q)); cmin = Math.min(x, Math.min(p, q)); best = Math.max(best, cmax); } return best; } }7 Best sightseeing pair: maximise values[i] + values[j] + i - j for i < j.
mediumRewrite the score as (values[i] + i) + (values[j] - j). Scan j from left to right, keeping the best value of values[i] + i seen so far; for each j the best score is that best plus values[j] - j. This is Kadane-style: carry the best prefix quantity forward. Time O(n), space O(1).. Edge cases: two elements, large gaps that penalise distance, equal values.
pythondef max_score_sightseeing_pair(v): best_i, ans = v[0], 0 for j in range(1, len(v)): ans = max(ans, best_i + v[j] - j) best_i = max(best_i, v[j] + j) return ansjavaimport java.util.*; class Solution { static int maxScoreSightseeingPair(int[] v) { int bestI = v[0], ans = 0; for (int j = 1; j < v.length; j++) { ans = Math.max(ans, bestI + v[j] - j); bestI = Math.max(bestI, v[j] + j); } return ans; } }8 Maximum sum of a subarray with at least k elements.
mediumKadane alone cannot enforce a minimum length. Use prefix sums: for each end i with at least k elements, the best subarray ending at i starts at the prefix with the smallest value among indices up to i - k. Track that minimum as you advance and take the maximum of p[i] minus it. Time O(n), space O(n) for the prefix array (O(1) with a rolling sum).. Edge cases: k equal to the array length (the whole array), all negative values, k = 1 (plain Kadane).
pythondef max_sum_at_least_k(a, k): n = len(a) p = [0] * (n + 1) for i in range(n): p[i + 1] = p[i] + a[i] best, min_pre = float('-inf'), float('inf') for i in range(k, n + 1): min_pre = min(min_pre, p[i - k]) best = max(best, p[i] - min_pre) return bestjavaimport java.util.*; class Solution { static long maxSumAtLeastK(int[] a, int k) { int n = a.length; long[] p = new long[n + 1]; for (int i = 0; i < n; i++) p[i + 1] = p[i] + a[i]; long best = Long.MIN_VALUE, minPre = Long.MAX_VALUE; for (int i = k; i <= n; i++) { minPre = Math.min(minPre, p[i - k]); best = Math.max(best, p[i] - minPre); } return best; } }9 Maximum subarray sum with at most one element deleted (at least one element must remain).
hardKeep two running values. no_del is the best sum ending here with no deletion (plain Kadane). one_del is the best ending here with one deletion: either delete the current element (take the previous no_del) or keep it and extend a previous one_del. Update one_del before no_del, since it uses the old no_del. For [1,-2,0,3] the answer is 4 by deleting -2. Time O(n), space O(1).. Edge cases: all negative values, a single element (no deletion possible), deleting an endpoint.
pythondef maximum_sum(a): no_del, one_del, best = a[0], float('-inf'), a[0] for x in a[1:]: one_del = max(one_del + x, no_del) no_del = max(no_del + x, x) best = max(best, no_del, one_del) return bestjavaimport java.util.*; class Solution { static int maximumSum(int[] a) { int noDel = a[0], best = a[0]; int oneDel = Integer.MIN_VALUE / 2; for (int i = 1; i < a.length; i++) { oneDel = Math.max(oneDel + a[i], noDel); noDel = Math.max(noDel + a[i], a[i]); best = Math.max(best, Math.max(noDel, oneDel)); } return best; } }10 Maximum sum rectangle in a 2D matrix.
hardFix a pair of top and bottom rows and add up each column between them into a 1D array of column sums. The best rectangle with exactly those rows is the maximum subarray of that array, found with Kadane. Try every pair of rows and keep the best. Reducing 2D to 1D is the key idea. Time O(R^2 * C), space O(C).. Edge cases: a single row or column, all negative values (the largest element), non-square input.
pythondef max_sum_rectangle(m): R, C = len(m), len(m[0]) best = float('-inf') for top in range(R): col = [0] * C for bottom in range(top, R): for j in range(C): col[j] += m[bottom][j] cur = col[0] best = max(best, cur) for x in col[1:]: cur = max(x, cur + x) best = max(best, cur) return bestjavaimport java.util.*; class Solution { static int maxSumRectangle(int[][] m) { int R = m.length, C = m[0].length, best = Integer.MIN_VALUE; for (int top = 0; top < R; top++) { int[] col = new int[C]; for (int bottom = top; bottom < R; bottom++) { for (int j = 0; j < C; j++) col[j] += m[bottom][j]; int cur = col[0]; best = Math.max(best, cur); for (int j = 1; j < C; j++) { cur = Math.max(col[j], cur + col[j]); best = Math.max(best, cur); } } } return best; } }
Frequently asked questions
Is Kadane's algorithm dynamic programming?
Yes. The state is the best subarray sum ending at each index, and the recurrence is best_here = max(a[i], best_here + a[i]). Because only the previous value is needed, it needs O(1) space.
What if all numbers are negative?
The answer is the largest single element. Initialise with the first element rather than 0 so that this case works, unless an empty subarray is allowed.
Why do product problems need both a maximum and a minimum?
A negative number multiplied by the current minimum (a large negative) can become the new maximum, so you must keep both ends of the range.
Can I print the subarray itself?
Yes. Record the start index whenever you restart the running sum, and update the best start and end whenever the running sum beats the best.
What is the difference between Kadane and sliding window?
Sliding window needs a monotonic condition, usually positive numbers. Kadane handles negatives because it decides per element to restart. See sliding window questions.
Related guides
- Dynamic Programming Interview Questions
- Array interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Sliding window interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
- Matrix interview questions with worked solutions
More in DSA Interview Questions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions