Kadane's Algorithm: Why It's DP, Not Greedy
Kadane's algorithm finds the contiguous subarray with the largest sum in a single pass, replacing a brute-force scan that checks every possible subarray with one that runs in O(n) time and O(1) extra space. At each index it asks one question: does extending the running subarray from the previous position beat starting fresh at the current element? That single comparison, repeated once per element, is the entire algorithm. It gets classified as dynamic programming rather than greedy, and the distinction matters more than it sounds, because an interviewer who asks you to justify why a rule that looks greedy actually produces the optimal answer is testing whether you understand why the algorithm works, not just whether you memorized the four lines of code. This guide covers a full step-by-step trace, code in three languages, how to recover the actual subarray, the all-negative edge case, the two follow-up variants interviewers ask, and the greedy-versus-DP question directly.
What Problem Does Kadane's Algorithm Actually Solve?
Kadane's algorithm solves the maximum subarray problem: given an array of integers that can include negative numbers, find the contiguous run of elements whose sum is the largest possible. Take [-2, 1, -3, 4, -1, 2, 1, -5, 4] as the working example for this entire guide. The answer is the subarray [4, -1, 2, 1], which sums to 6, and no other contiguous run in that array beats it.
The word "contiguous" is doing real work in that definition, and it is the detail that trips people up first. You cannot just pick the largest positive numbers wherever they appear and add them together, because that ignores the constraint that the chosen elements have to sit next to each other in the original order. Picking 4, 2, 1, and 4 from the example array would sum to 11, but those four values are not a contiguous run, so that selection is not a valid answer to this problem. Every candidate answer has to be a single unbroken slice of the array, which is exactly the constraint that makes a running-sum approach like Kadane's algorithm the right tool instead of a sorting or selection trick.
Why Isn't a Brute Force Scan Good Enough?
A brute force scan is not good enough because it re-examines overlapping work for every pair of start and end indices, which costs far more time than the problem actually requires. The most direct brute force checks every possible pair of a start index and an end index, sums the elements between them, and keeps the largest sum seen, which costs O(n cubed) once you count the inner summation loop. Precomputing a running prefix sum array removes that inner loop and gets the cost down to O(n squared), since each pair of indices can now be checked with a single subtraction instead of a fresh sum.
O(n squared) is a real improvement, but it still means a million-element array requires roughly a trillion operations, which is not acceptable for anything resembling real input size, and it is exactly the kind of answer an interviewer accepts as a starting point before asking you to do better. The gap between O(n squared) and O(n) is where Kadane's algorithm earns its place: it reaches the same answer in a single left-to-right pass, without ever comparing two indices directly against each other.
How Does Kadane's Algorithm Work, Step by Step?
Kadane's algorithm works by tracking two running values as it scans the array once from left to right: the best sum of a subarray that ends exactly at the current index, and the best sum seen anywhere so far. At each index, the running subarray either grows by absorbing the current element or gets abandoned in favor of starting a brand new subarray at that element, and the choice is decided by a single comparison: is the current element on its own larger than the current element plus whatever the running subarray was already worth? Whichever is larger becomes the new running sum, and the overall best is updated if the running sum just beat it.
Running that logic against [-2, 1, -3, 4, -1, 2, 1, -5, 4] plays out one index at a time, where "current" tracks the best subarray ending exactly at that index and "best" tracks the largest current value seen so far. At index 0 both values start at -2, the only element seen. At index 1, extending would give -2 + 1 = -1, but 1 alone is larger, so current resets to 1 and best rises to match it. At index 2, extending gives 1 + -3 = -2, which still beats starting fresh at -3 alone, so current becomes -2, but best holds at 1 since -2 does not beat it.
From index 3 onward the run pays off. Extending at index 3 gives -2 + 4 = 2, but 4 alone is larger, so current resets to 4 and best climbs to 4 with it. At index 4, extending gives 4 + -1 = 3, which beats starting over at -1 alone, so current becomes 3 while best stays at 4. At index 5, extending gives 3 + 2 = 5, a new high, so both current and best become 5. At index 6, extending gives 5 + 1 = 6, and both values climb to 6. At index 7, extending gives 6 + -5 = 1, which still beats starting fresh at -5 alone, so current drops to 1, but best holds at 6. At the final index, extending gives 1 + 4 = 5, which beats starting fresh at 4 alone, so current rises to 5, but it never catches the 6 locked in three steps earlier, and 6 is the answer the algorithm returns.
The running sum resets whenever the current element alone beats carrying the previous run forward, and the best value only moves when the running sum actually surpasses it, which is exactly why the algorithm needs two separate variables instead of one.
What Does the Code Look Like in Python, Java, and JavaScript?
The code looks nearly identical across languages because the entire algorithm is one loop and two comparisons, with no data structure beyond a pair of variables. Here it is in Python:
def max_subarray(nums):
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sumThe same logic in Java:
public int maxSubArray(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}And in JavaScript:
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}All three initialize both running values to the first element rather than to zero, which matters more than it looks. Starting at zero would silently accept an empty subarray as a candidate answer, which produces the wrong result the moment every value in the array is negative, an edge case covered in full further down.
Is Kadane's Algorithm Greedy or Dynamic Programming?
Kadane's algorithm is dynamic programming, not greedy, even though the single comparison at each step looks like a greedy rule at first glance. A greedy algorithm makes a locally optimal choice at each step and never revisits it, trusting without proof that a sequence of locally optimal choices adds up to a globally optimal answer. Dynamic programming instead defines a precise subproblem, in this case "the best sum of a subarray that ends exactly at index i", and derives each subproblem's answer strictly from the answer to the previous one, which is the textbook definition of optimal substructure.
The "extend or restart" comparison at each index is not a greedy heuristic guessing at the future. It is directly evaluating the two only candidate answers to the subproblem at that index, extending the previous subarray or starting over, and keeping whichever one is larger, which is exactly what a dynamic programming transition does at every step of any DP table. It looks greedy only because the recurrence needs just the previous subproblem's value, so the full table of n subproblems compresses down to one running variable, the same trick that shrinks a full Fibonacci DP table down to two variables. Calling Kadane's algorithm greedy because it never backtracks confuses the absence of backtracking with the absence of a subproblem structure, and interviewers who ask this question are checking for that exact distinction.
How Do You Return the Actual Subarray, Not Just the Sum?
You return the actual subarray by tracking the start index of the current run alongside the running sum, and only committing that index to the answer once the running sum it produced actually becomes the new best.
def max_subarray_with_bounds(nums):
current_sum = max_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > current_sum + nums[i]:
current_sum = nums[i]
temp_start = i
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start, end = temp_start, i
return max_sum, nums[start:end + 1]The variable temp_start marks where the current running subarray began, and it only resets to the current index when the algorithm decides to abandon the old run and start fresh. The start and end values that get returned only update when the running sum actually beats the best seen so far, so they always describe the boundaries of the subarray that produced the winning sum rather than the boundaries of whatever subarray happens to be running at the end of the loop. Skipping this distinction is the most common bug in a live attempt at this extension: candidates update start on every reset instead of only when a new best is found, which silently returns the wrong subarray even though the sum itself comes out correct.
What Happens When the Array Is All Negative Numbers?
When the array is all negative numbers, Kadane's algorithm correctly returns the single least negative element, because starting fresh at any index is never worse than carrying a larger negative sum forward, and a subarray of length one is always a legal answer. Take [-8, -3, -6, -2, -5, -4] as a trace: the running sum starts at -8, then at index 1 it compares -3 against -8 + -3 = -11 and keeps -3 since it is larger, and the best-so-far updates to -3. At index 2, -6 is compared against -3 + -6 = -9, and -6 wins that comparison, so the running sum resets to -6, but the best-so-far stays at -3 since -6 does not beat it. The same pattern continues at each remaining index, and by the end the best-so-far settles on -2, the single least negative value in the array.
This edge case matters because a version of the algorithm that initializes its running values to zero instead of to the first element gets this case wrong: it would report a maximum sum of 0 from an empty subarray, which is not a valid answer if the problem requires at least one element to be chosen. Initializing both running values to nums[0] instead of 0, as every code sample in this guide does, is what keeps the all-negative case correct without any special-case branch.
How Does This Change for the Circular and Product Variants?
Two follow-ups build on the same running-comparison idea rather than replacing it. In the circular version, the array wraps around, so the winning subarray can span from near the end back around to near the beginning. The answer is either the ordinary Kadane's result on the array as written, or the total sum of the array minus the smallest possible subarray sum, since removing the smallest contiguous chunk from the total is equivalent to keeping everything that wraps around it. The one case that needs a manual check is an array where every value is negative: in that case the "total minus minimum" formula would incorrectly return zero, so the answer falls back to the plain non-circular result instead.
The maximum product subarray follow-up changes the algorithm in a subtler way: it needs two running values instead of one, a running maximum and a running minimum, because multiplying by a negative number can flip the most negative running product into the new largest one. A single running maximum, as used for the sum version, would lose track of a large negative product that is one multiplication away from becoming the best answer, so tracking the running minimum alongside the running maximum at every step is not optional bookkeeping, it is the entire reason the product variant needs different code rather than a copy-paste of the sum version.
What Should You Say Out Loud While You Solve It?
Say the dynamic programming framing before you write a single line of code: state that the running sum represents the best subarray ending at the current index, and that the comparison at each step chooses between extending that subarray and starting a new one at the current element. Naming the subproblem out loud before touching the keyboard is the single fastest way to signal that you are not pattern-matching from memory.
Once the code is on the screen, trace it by hand on a short example with at least one negative number, calling out the moment the running sum resets versus the moment it keeps growing, then mention the all-negative case verbally, since it is the edge case most likely to come up as a follow-up. Finally, state the complexity claim precisely: O(n) time because the array is scanned exactly once, and O(1) extra space because the solution only ever needs two variables regardless of how large the input gets. If the interviewer pushes on whether this is really dynamic programming, this is the moment to give the optimal-substructure explanation from earlier in this guide rather than waiting to be caught off guard by the question.
How Does Kadane's Algorithm Fit Into Your Broader Pattern Prep?
Kadane's algorithm is a specific, self-contained pattern, but it sits inside a broader dynamic programming skill that shows up across many other interview problems. Our guide to dynamic programming patterns covers how to recognize a DP problem in general and pick the right pattern family, and the "extend or restart" recurrence covered here is one concrete instance of the optimal-substructure thinking that guide builds from scratch.
It is also worth being precise about what Kadane's algorithm is not. It is easy to mistake it for sliding window, since both scan an array once from left to right, but sliding window tracks a range that can shrink from the left when a constraint is violated, while Kadane's algorithm never looks backward once it moves past an index; it only ever decides whether to keep extending or to abandon the run entirely. Our sliding window guide covers that shrink-from-the-left mechanic in depth, and reading the two side by side is the fastest way to stop confusing them under pressure. Our guide to spotting patterns before you code places both of these inside the small set of patterns that covers most of what actually shows up in a real interview, and our breakdown of time complexity is where the O(n) and O(1) claims made throughout this guide get the deeper treatment behind why interviewers accept them without a second thought.
Our curated question bank draws from real onsite reports rather than an unfiltered public archive, so the subarray and dynamic programming problems you find there reflect what companies are actually asking right now instead of a static list that stopped updating years ago.
Frequently Asked Questions
What is Kadane's algorithm?
Kadane's algorithm is a single-pass technique for finding the contiguous subarray with the largest sum inside an array that can contain negative numbers. It runs in O(n) time and O(1) extra space by tracking the best subarray ending at the current index and the best sum seen anywhere so far.
Is Kadane's algorithm greedy or dynamic programming?
Kadane's algorithm is dynamic programming, since the comparison at each step, extend the current run or start a new one, is a DP transition built on optimal substructure, not a greedy heuristic, even though it only needs one running variable instead of a full table.
What is the time and space complexity of Kadane's algorithm?
Kadane's algorithm runs in O(n) time, since it scans the array exactly once, and O(1) extra space, since it only tracks a running sum and a running best regardless of how large the input array is.
Does Kadane's algorithm work on an array of all negative numbers?
Yes, as long as both running values are initialized to the first element rather than to zero. Done that way, the algorithm correctly returns the single least negative element, since a subarray of length one is always a valid answer and starting fresh never does worse than carrying a larger negative sum forward.
Is Kadane's algorithm the same as sliding window?
No, sliding window maintains a range that can shrink from the left when a constraint breaks, while Kadane's algorithm never looks backward once it passes an index; it only decides whether to extend the current run or abandon it and start over at the current element.
How do you adapt Kadane's algorithm for a circular array?
Run the standard algorithm to get the maximum non-circular sum, then separately find the minimum subarray sum using the same technique with the comparisons flipped, and subtract that minimum from the array's total sum to get the best circular answer. Take the larger of the two results, except when every value in the array is negative, in which case the plain non-circular answer is the correct one.