Kadane's Algorithm Explained — Maximum Subarray Sum in O(n)
Every few months, a new developer stumbles into a coding interview, sees the 'Maximum Subarray' problem, and freezes. It looks deceptively simple — find the contiguous subarray with the largest sum — but the brute-force instinct leads you straight into O(n²) or O(n³) territory. At Google-scale, that's the difference between a query completing in milliseconds versus timing out entirely. This is a problem that appears in financial analytics, signal processing, genomics (finding regions of DNA with high expression), and anywhere you need to identify the 'hottest streak' inside a sequence of data.
The naive approach checks every possible start and end pair, computing the sum each time. With a 10,000-element array, that's roughly 50 million operations. Kadane's Algorithm — named after computer scientist Jay Kadane who formalized it in 1984 — solves the exact same problem in a single linear pass. No nested loops. No backtracking. It works by maintaining a running bet: keep extending the current subarray only as long as it's beneficial to do so, and restart the moment your baggage outweighs your potential.
By the end of this article you'll understand not just the code, but the decision logic underneath it — well enough to explain it on a whiteboard, handle tricky edge cases (all-negative arrays, single elements), and confidently extend it to track which subarray produced the maximum sum, not just what the sum was.
The Core Intuition — Why the Greedy Decision Works
Before touching code, let's lock in the mental model. At every index i, you face exactly one binary choice: does the current element join the existing subarray, or does it become the start of a brand-new one?
The rule is beautifully simple: if your running sum so far is negative, it's dead weight. Carrying it into the next element can only make that element's contribution worse. So you drop it. You set your running sum equal to the current element and start fresh. If your running sum is positive, it's a booster — keep it.
This is a greedy decision, and it's correct because the optimal subarray can never benefit from a negative prefix. Think about it: if the subarray [3, -5, 2, 4] were the optimal answer, you could always remove the [3, -5] prefix (which sums to -2) and get [2, 4] with a larger sum. That contradiction proves negative prefixes can never be part of the true maximum subarray.
The algorithm tracks two values at all times: currentSum (the best sum ending at the current position) and maxSumFound (the global best seen so far). Every step, you update both. When the loop finishes, maxSumFound is your answer.
public class KadaneBasic { /** * Finds the maximum sum of any contiguous subarray. * Uses Kadane's Algorithm — O(n) time, O(1) space. * * @param profits array of integers representing daily gains/losses * @return the highest achievable sum from any contiguous run */ public static int findMaxSubarraySum(int[] profits) { // Seed both trackers with the first element. // We can't use 0 here — if all numbers are negative, // the real answer might be negative too (see Gotchas). int currentSum = profits[0]; int maxSumFound = profits[0]; // Start from index 1 — we've already seeded with index 0. for (int day = 1; day < profits.length; day++) { // Core decision: extend the current run, or start fresh today? // If currentSum is negative, profits[day] alone beats extending. currentSum = Math.max(profits[day], currentSum + profits[day]); // Did we just beat our personal record? maxSumFound = Math.max(maxSumFound, currentSum); } return maxSumFound; } public static void main(String[] args) { // Classic example: best streak is [4, -1, 2, 1] summing to 6 int[] dailyProfits = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println("Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]"); System.out.println("Max subarray sum: " + findMaxSubarraySum(dailyProfits)); // Edge case: all negatives — answer is the least negative element int[] allLosses = {-8, -3, -6, -2, -5}; System.out.println("\nInput (all negatives): [-8, -3, -6, -2, -5]"); System.out.println("Max subarray sum: " + findMaxSubarraySum(allLosses)); // Edge case: single element int[] oneDay = {42}; System.out.println("\nInput (single element): [42]"); System.out.println("Max subarray sum: " + findMaxSubarraySum(oneDay)); } }
Max subarray sum: 6
Input (all negatives): [-8, -3, -6, -2, -5]
Max subarray sum: -2
Input (single element): [42]
Max subarray sum: 42
Tracking the Actual Subarray — Not Just the Sum
The basic version tells you the maximum sum, but real-world use cases often need to know which subarray produced it. Imagine a financial dashboard that needs to highlight the exact date range of peak profitability — the number alone isn't enough.
Extending Kadane's to track indices takes almost no extra code. You record a potentialStart index whenever you decide to restart (i.e., when starting fresh beats extending). The moment that fresh start leads to a new global maximum, you commit it: you update bestStart, bestEnd, and maxSumFound together as an atomic snapshot.
This is a subtle but important pattern. You only want to commit the start index when you've confirmed it produced a better result, not optimistically when you reset. That distinction separates a correct implementation from a buggy one that snaps the wrong start index.
public class KadaneWithIndices { static class SubarrayResult { int maxSum; int startIndex; int endIndex; SubarrayResult(int maxSum, int startIndex, int endIndex) { this.maxSum = maxSum; this.startIndex = startIndex; this.endIndex = endIndex; } @Override public String toString() { return String.format( "Max Sum: %d | Start Index: %d | End Index: %d", maxSum, startIndex, endIndex ); } } /** * Kadane's Algorithm extended to return the subarray boundaries. * Still O(n) time, O(1) space — we just track three extra integers. */ public static SubarrayResult findMaxSubarray(int[] values) { int currentSum = values[0]; int maxSumFound = values[0]; // potentialStart: where the CURRENT run began (tentative) int potentialStart = 0; // bestStart/bestEnd: boundaries of the CONFIRMED best run int bestStart = 0; int bestEnd = 0; for (int index = 1; index < values.length; index++) { // If starting fresh at 'index' beats extending the current run... if (values[index] > currentSum + values[index]) { // ...reset the running sum and mark a tentative new start. currentSum = values[index]; potentialStart = index; // candidate — only confirmed if it beats maxSumFound } else { // Extend the current run. currentSum += values[index]; } // If this is a new global best, lock in the subarray boundaries. if (currentSum > maxSumFound) { maxSumFound = currentSum; bestStart = potentialStart; // NOW we commit the start bestEnd = index; // current position is the new end } } return new SubarrayResult(maxSumFound, bestStart, bestEnd); } public static void main(String[] args) { int[] stockReturns = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; SubarrayResult result = findMaxSubarray(stockReturns); System.out.println("Full array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]"); System.out.println(result); // Print the actual winning subarray System.out.print("Winning subarray: ["); for (int i = result.startIndex; i <= result.endIndex; i++) { System.out.print(stockReturns[i]); if (i < result.endIndex) System.out.print(", "); } System.out.println("]"); // Second example: peak at the end of the array int[] lateBloom = {1, 2, -10, 3, 7, -1, 8}; System.out.println("\nFull array: [1, 2, -10, 3, 7, -1, 8]"); System.out.println(findMaxSubarray(lateBloom)); } }
Max Sum: 6 | Start Index: 3 | End Index: 6
Winning subarray: [4, -1, 2, 1]
Full array: [1, 2, -10, 3, 7, -1, 8]
Max Sum: 17 | Start Index: 3 | End Index: 6
Kadane's vs. Brute Force vs. Divide and Conquer — Choosing Wisely
Understanding why Kadane's is the right choice requires knowing what you're giving up and getting compared to the alternatives.
The brute-force approach uses two nested loops to check every (start, end) pair. It's O(n²) and straightforward to reason about, which makes it fine for arrays under a few hundred elements in non-critical paths. Divide and Conquer solves the problem in O(n log n) — better than brute force, but still worse than Kadane's. Its advantage is that it's parallelizable: you can split the array across multiple cores and merge results, which matters in distributed systems processing massive datasets.
Kadane's wins on pure time complexity and simplicity for the single-machine case. One pass, two variables, done. The only scenario where you'd reach for Divide and Conquer over Kadane's is when you need to run this computation across distributed partitions where a central linear scan isn't possible — think MapReduce jobs over terabyte-scale log files.
For coding interviews, Kadane's is the expected answer the moment you see 'maximum subarray.' Mentioning the Divide and Conquer alternative shows depth and will genuinely impress a senior interviewer.
public class BruteForceVsKadane { /** * Brute Force: O(n^2) — check every contiguous subarray. * Correct, but painfully slow on large inputs. */ public static int bruteForceMaxSum(int[] values) { int globalMax = values[0]; for (int start = 0; start < values.length; start++) { int runningSum = 0; for (int end = start; end < values.length; end++) { runningSum += values[end]; globalMax = Math.max(globalMax, runningSum); } } return globalMax; } /** * Kadane's: O(n) — single pass, same correct answer. */ public static int kadaneMaxSum(int[] values) { int currentSum = values[0]; int globalMax = values[0]; for (int index = 1; index < values.length; index++) { currentSum = Math.max(values[index], currentSum + values[index]); globalMax = Math.max(globalMax, currentSum); } return globalMax; } public static void main(String[] args) { int[] testData = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; long bruteStart = System.nanoTime(); int bruteResult = bruteForceMaxSum(testData); long bruteTime = System.nanoTime() - bruteStart; long kadaneStart = System.nanoTime(); int kadaneResult = kadaneMaxSum(testData); long kadaneTime = System.nanoTime() - kadaneStart; System.out.println("=== Results ==="); System.out.println("Brute Force answer: " + bruteResult + " | Time: " + bruteTime + " ns"); System.out.println("Kadane's answer: " + kadaneResult + " | Time: " + kadaneTime + " ns"); System.out.println("Both match: " + (bruteResult == kadaneResult)); } }
Brute Force answer: 6 | Time: 4821 ns
Kadane's answer: 6 | Time: 1203 ns
Both match: true
| Aspect | Brute Force | Divide & Conquer | Kadane's Algorithm |
|---|---|---|---|
| Time Complexity | O(n²) | O(n log n) | O(n) |
| Space Complexity | O(1) | O(log n) stack | O(1) |
| Code Complexity | Simple | Moderate | Simple |
| Handles All-Negatives | Yes | Yes | Yes (if seeded correctly) |
| Parallelizable | No | Yes | No (sequential by design) |
| Interview Expectation | Starting point only | Bonus depth answer | Primary expected answer |
| Real-world fit | Small arrays, prototyping | Distributed/MapReduce jobs | Standard single-machine use |
🎯 Key Takeaways
- Kadane's core decision is:
currentSum = Math.max(element, currentSum + element)— this single line encodes the entire greedy insight that a negative prefix can never help you. - Always seed currentSum and maxSumFound with the first element, not with 0 — seeding with 0 silently breaks the all-negative case and gives a wrong answer without throwing an error.
- When extending to track subarray indices, only commit bestStart when you confirm a new global maximum — premature commitment on reset is the most common bug in the extended version.
- Kadane's is O(n) time and O(1) space — if an interviewer asks about the trade-off vs. Divide and Conquer, mention that D&C is more parallelizable for distributed systems, while Kadane's wins for single-machine linear scans.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Initializing currentSum and maxSumFound to 0 — Your algorithm returns 0 for an all-negative array like [-4, -1, -7] instead of -1 — Fix it by seeding both variables with the first element (index 0) and starting your loop at index 1. The empty subarray (sum = 0) is only valid if the problem explicitly allows it.
- ✕Mistake 2: Forgetting to update maxSumFound inside the loop — You only see the currentSum at the very end, which only reflects the last element's contribution, not the global peak — Fix it by placing
maxSumFound = Math.max(maxSumFound, currentSum)inside every loop iteration, immediately after updating currentSum. - ✕Mistake 3: Committing the subarray start index too early when tracking boundaries — You set bestStart = potentialStart the moment you reset, not when you confirm a new maximum, so the start index points to a later fresh run even though an earlier subarray produced the highest sum — Fix it by only updating bestStart (and bestEnd) inside the
if (currentSum > maxSumFound)block, not inside the reset branch.
Interview Questions on This Topic
- QWalk me through Kadane's Algorithm step by step on the array [-2, 1, -3, 4, -1, 2, 1, -5, 4] — what is currentSum and maxSumFound at each index?
- QHow would you modify Kadane's Algorithm to return the actual subarray (start and end indices), not just the maximum sum? What is the tricky part of tracking the start index correctly?
- QWhat does Kadane's Algorithm return if every element in the array is negative — and why does the initialization strategy matter for correctness? How would your answer change if the problem allowed choosing an empty subarray?
Frequently Asked Questions
Does Kadane's Algorithm work when all numbers in the array are negative?
Yes, but only if you initialize correctly. Seed currentSum and maxSumFound with the first element (not with 0). That way, on an array like [-8, -3, -6], the algorithm correctly returns -3 — the least negative value. Seeding with 0 would return 0, which represents an empty subarray and is almost always the wrong answer for this class of problem.
What is the difference between Kadane's Algorithm and dynamic programming?
Kadane's Algorithm is a specific application of dynamic programming. The DP state is: 'what is the maximum subarray sum ending exactly at index i?' Kadane's solves this with the recurrence dp[i] = max(arr[i], dp[i-1] + arr[i]). Because each state only depends on the previous one, you can collapse the DP table into a single variable (currentSum), which is why it runs in O(1) space.
Can Kadane's Algorithm handle a 2D array (maximum subarray in a matrix)?
Not directly, but you can extend it. The standard approach is to fix the left and right column boundaries, then compress each row within those boundaries into a single value by summing across columns. This gives you a 1D array on which you run Kadane's normally. Repeating for all O(n²) column boundary pairs gives an overall O(n³) solution for an n×n matrix.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.