Maximum subarray and Kadane's algorithm

Why it matters

"Find the stretch of days with the biggest total gain" is one of the most asked array questions in interviews, and it shows up in real systems more often than you might expect. A trader wants the best period to hold a stock. A fitness app wants the longest stretch of workouts that added the most calories burned. A network monitor wants the window of traffic that rose the most. Each of these is a question about a contiguous part of an array, a block of neighbouring values, and each has the same answer shape: one number, the largest total any such block can reach.

The obvious way to answer checks every block. There are about n squared blocks, and adding each one costs time, so the naive method is O(n cubed) if you add afresh and O(n squared) if you keep a running total. Kadane's algorithm solves the problem in one pass, with two variables. It is short, it is famous, and it is the answer interviewers expect you to reach after a little thought. This lesson builds it from the first principle, traces it step by step, and then adds the start and end positions that many problems also ask for.

The idea: carry a score only while it helps

Imagine you are walking a path with numbers written on the stones. Each stone adds a number to your score: a positive stone adds points, a negative stone takes points away. You start at the first stone and walk forward. At each stone you have two choices. You can keep the score you carried in from behind and add this stone's number to it. Or you can drop everything and start a fresh score at this stone.

Which choice is better? If the score you carried in is negative, it only hurts. Adding a negative number to a negative score makes it worse, and you would do better to start fresh here. If the score you carried in is positive, keeping it helps, because you are adding to something good. The decision depends on one question: is what I carried in worth keeping? That is the whole idea. Keep the running score when it is useful, and restart it when it is not.

While you walk, you also remember the best score you have seen at any stone. The answer is the best score over the whole walk, because the best stretch might end at any stone, not necessarily the last.

The precise version

Let a be the array. Define cur as the best total of a block that ends at the current position. Define best as the best total of any block seen so far. Start with cur and best both equal to a[0]. For each later index i, do two steps:

cur = max(a[i], cur + a[i])
best = max(best, cur)

The first line is the decision. Either the block starts at a[i] by itself, or it extends the block that ended at i - 1. The max picks the bigger of the two. The second line records the best block found so far. After the loop, best holds the answer.

Notice that max(a[i], cur + a[i]) is the same as the rule from the story: if cur is negative, then cur + a[i] is less than a[i], so the max picks a[i] and drops the old block. If cur is zero or positive, the max keeps the old block and adds to it. Some programs write the rule as "if cur is negative, restart", which is equivalent and easier to read at first.

A tiny example with the rule in action

Take the array -2, 1, -3, 4, -1, 2, 1, -5, 4. Before reading the trace, guess the answer. It is the sum of a contiguous block, and the block is short and easy to spot once you look for the bulge in the middle. Then check your guess against the table.

The answer is 6. The block that gives it is 4, -1, 2, 1, from index 3 to index 6. The row at index 3 is the restart: the old running score of -2 was negative, so the algorithm dropped it and started at 4. The table makes one thing plain. The block that produces the answer can start fresh anywhere, and the algorithm finds it without checking all blocks.

Step through the table above. Watch the two rows, one for the best block ending here and one for the best block so far. The table is an example of dynamic programming, which means building an answer from smaller answers you already know. Each cell of the cur row is built from the cell before it, and the best row is built from the best cell before it and the current cur.

The figure below shows the same trace on a diagram. The highlighted cells are the block that gives the answer.

Nine values with the current and best rows under them, and the slice 4 -1 2 1 highlighted

Why the one-pass rule is correct

Interviewers often ask you to prove that an algorithm is correct, not only to show that it runs. For Kadane's algorithm the proof rests on one promise that you can state in plain words. After step i, the variable cur holds the largest sum of a block that ends exactly at index i. If that promise holds at every step, the answer is right, because the best block overall ends at some index, and at that index cur already holds its sum.

Take the first step. The only block that ends at index 0 is the block that holds a[0] alone, so cur starts as a[0]. The promise holds.

Now suppose the promise holds for index i - 1. Look at every block that ends at index i. Each such block is either the single value a[i], or a longer block that ends at i - 1 and then takes a[i] as its last value. The longer blocks have sums equal to some block ending at i - 1, plus a[i]. The best of those longer blocks is therefore the best block ending at i - 1, which is the old cur, plus a[i]. So the best block ending at i is the larger of two numbers: a[i] alone, or the old cur plus a[i]. That is exactly the max in the rule, and the promise holds at i.

The second line, best = max(best, cur), needs an equally simple argument. Every block of the array ends at some index, and cur at that index is at least the sum of that block. So the running maximum of cur is at least the sum of every block by the time the walk ends. And best only ever holds a sum that some real block achieves, so it cannot be too large.

Put the two facts together and the result follows. Each step is correct given the step before, and the first step is correct. A chain of correct steps ends with a correct answer. Mathematicians call this proof method induction, and you do not need the name to use the idea. Say the two facts out loud in an interview, and you have proved the algorithm.

Notice what the proof did not need. It did not need the array to be sorted, or positive, or to contain any particular values. It works for any sequence of numbers, which is why the algorithm is so general. The only assumption that matters is that the answer must contain at least one value, which is why the start is a[0] and not 0.

The program

Here is Kadane's algorithm as a complete program. It reads n and then the values, and prints the maximum subarray sum. It uses long long for the running values, for a reason the common mistakes section explains.

Type this into the Input box:

9
-2 1 -3 4 -1 2 1 -5 4

The program prints:

maximum subarray sum = 6

The program starts both values at a[0] and then loops from index 1. Starting the loop at 1 is correct because the first value was already used. The loop body is the two lines from the rule. The max function comes from <algorithm>, and both of its arguments must have the same type, which is why a and cur are both long long. Mixing int and long long in a max call is a compile error, and the mistakes section shows the exact message.

The program does not know where the best block starts or ends. It knows only the total. If the question asks for the total alone, this is the full answer. Many interviewers then ask for the positions, which is the next program.

Tracking where the block starts and ends

To print the best block's range, you need to track two more things. You need the start of the current block, and you need the start and end of the best block. The restart decision sets the current start. The best update records the best start and the current index as the end.

Type the same nine values into the Input box. The program prints:

sum 6 from index 3 to 6

This version writes the rule as "if cur is negative, restart", which is the same decision as the max in the first program. If cur is zero, the program keeps extending. A zero-sum prefix does not hurt, so extending is harmless, and the best block is still found. The tie-breaking rule matters if a question asks for a specific block when two blocks have the same total. Read the statement carefully, and state which block you return.

Trace the start and end. The first restart is at index 1, because the running score of -2 is negative. The program sets curStart to 1, and cur becomes 1. Index 2 keeps the block, so cur is -2. At index 3 the score is negative, so the program restarts there and sets curStart to 3. The best total is then updated along the way, and the final best is 6 with bestStart equal to 3 and bestEnd equal to 6. The ranges agree with the table from earlier.

Check the code line by line when you read it. The cur > best update is strict, so a tie keeps the earlier block. That is the choice made here, and a different problem might want the longer block instead. The point is that the code makes the choice visible, and you can change it on purpose.

Why starting at zero breaks everything

Beginners often write cur = 0 and best = 0 at the start, to avoid thinking about the first element. For arrays that contain at least one positive value, the answer is still often right, but the reason is luck. For an array with only negative values, the program prints 0, which is not even a sum of any block. The next program shows the difference side by side.

The program prints:

start at 0 gives 0
start at a[0] gives -2

The wrong version never leaves 0, because every value is negative. The first step gives wrongCur equal to -8, and wrongBest stays at 0, because 0 is bigger. Every later step keeps wrongBest at 0. The right version starts from a[0], which is -8, and walks through the list. The best single value is -2, which is the least negative number in the list, and that is the correct answer. A problem that asks for "the maximum subarray" requires at least one element in the block. The answer must be a real sum, and -2 is one.

This is the most important detail in the lesson, and interviewers test it on purpose. Ask yourself what your answer should be when every value is negative. If the answer is "the largest single value", start from the first element. If the problem explicitly allows an empty block, the answer can be 0, but then say so in the first sentence of your answer.

A related pattern: a window of fixed length

Kadane's algorithm finds the best block of any length. A related question fixes the length. Find the largest total of any block of exactly k values. A nested loop would add each block afresh, which is O(n times k). A sliding window does better. Compute the first block's total, then slide it one step to the right. Each slide adds the new value on the right and removes the old value on the left, so each step costs one addition and one subtraction.

Type this into the Input box:

8 3
2 1 5 1 3 2 8 1

The program prints:

best window of 3 = 13

The windows of three values have totals 8, 7, 9, 6, 13 and 11. The largest is 13, from the values 3, 2 and 8. The sliding window touches each value a fixed number of times, so the whole run is O(n). Notice the difference from Kadane: the window has a fixed length, and Kadane's block can be any length. Choose the tool from the wording. The phrase "exactly k values" means a window. The phrase "any contiguous part" means Kadane.

What happens inside the one-pass loop

Kadane's loop reads each value once and does two comparisons and an addition. The two variables cur and best live in the processor's registers during the loop, so the work per value is a few instructions and no extra memory. This is why the space cost is O(1). The time cost is O(n), because the loop runs once over the array. That pair of numbers, O(n) time and O(1) extra space, is what you should say when asked.

The long long type deserves attention. Each value in the array might fit in an int, but the running total can grow past two billion when there are many large values. A signed overflow in C++ is undefined behaviour, which means the program can print any number, including a wrong one that looks plausible. Using long long for cur and best avoids this for any input the course uses. When an interviewer asks about overflow, mention long long and say that the sum of n values of size up to M can reach n times M.

The table in the figure earlier is the memory that the loop does not need. You do not store the whole row. Each step needs only the previous cur, which is one variable, and the best so far, which is another. Students often write a full array of cur values for clarity, and that is fine for learning. In an interview, the two variables are the better answer, and you should say that the table is available if the interviewer wants to see it.

A worked example with real prices

Suppose a shop's stock closes at 7, 1, 5, 3, 6 and 4 on six days in a row. You want the largest profit from buying on one day and selling on a later day. The question sounds different from the subarray question, but it becomes one with a small change of view.

Take the difference between each day and the day before. These are the daily changes. The first is 1 minus 7, which is -6. The next is 5 minus 1, which is 4. Then 3 minus 5 gives -2, 6 minus 3 gives 3, and 4 minus 6 gives -2. A block of consecutive changes adds up to the change in price across the days that block covers. So the best profit is the largest block sum of the changes.

Run Kadane's rule on -6, 4, -2, 3, -2. Start with cur and best at -6. At the second change, cur plus 4 is -2, which is less than 4 by itself, so the rule restarts there: cur becomes 4 and best becomes 4. At the third change cur is 4 and the value is -2, so cur becomes 2, and best stays at 4. At the fourth change the value 3 gives cur equal to 5, which is the new best. At the fifth change the value -2 gives cur equal to 3, and the best stays at 5. The answer is 5.

The block that gives 5 is the changes 4, -2 and 3. Those three changes cover the moves from day 1 to day 4, counting days from 0. The price on day 1 is 1, and the price on day 4 is 6. Buy at 1 and sell at 6, and the profit is 5, which matches the block sum.

Two details matter for the interview answer. First, the buy must come before the sell, and the difference method respects that automatically, because each change is measured forward in time. Second, if every change is negative, the best profit is 0 when you are allowed to skip trading. Interviewers often add that condition. The fix is to start best at 0 in that version, which changes the problem, so state the change out loud before you code it.

There is a second method that needs no table of changes. Walk through the prices once. Keep the lowest price seen so far, and at each day subtract that lowest price from today's price to get a possible profit. Keep the largest profit. That method is also O(n) time and O(1) extra space, and it shows the same idea from another side: the best profit on a day is that day's price minus the lowest price before it.

Explaining it in an interview

A good answer about Kadane's algorithm has a clear order. Name the problem, then the pattern, then the one-line rule, then the cost, then the edge case. Candidates who follow this order usually get the follow-up questions they can answer, because the interviewer hears the plan before the code.

A short script works well. Begin with the problem: this asks for the largest sum of a contiguous block. Name the pattern: I will walk the array once and keep two values. The first is the best block that ends at the current index. The second is the best block seen so far. At each index, the block either restarts at this value or extends the previous block, whichever sum is larger. The answer is the best value seen. Give the cost: one pass, so O(n) time, and two variables, so O(1) extra space.

Then state the edge case before the interviewer has to ask. If every value is negative, the answer is the largest single value, so I start from the first element rather than from zero. Finish with the follow-ups, one sentence each. If you need the positions, track where the current block started and update it on each restart. If the array is circular, also compare with the total minus the smallest block, unless all values are negative.

Practise this script out loud, at least three times, with a different array each time. The most common reasons candidates lose marks are not in the code. They are a long silence before the first sentence, a missing edge case that the interviewer had to point out, and a plan that was never said aloud. A clear plan spoken at the start fixes all three.

Common mistakes and what they look like

Starting from zero

This is the mistake from the program above. It gives 0 for all-negative input, and it is the first thing to test. Start from a[0].

Forgetting to update best after the loop

Some programs update best only inside the restart branch. The best block can end at the last index, and then it is never recorded. Update best on every step, after the cur decision, as the rule says.

Returning cur instead of best

cur is the best block ending at the last index, which is not always the best block overall. For the array -2, 1, -3, 4, -1, 2, 1, -5, 4, the last cur is 5, but the answer is 6. Return best.

Mixing int and long long in max

This is a compile error, not a wrong answer, and it is easy to produce. The message from g++ looks like this:

k1.cpp:6:19: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, long long int)'
    6 |     cur = std::max(a[1], cur + a[1]);
      |           ~~~~~~~~^~~~~~~~~~~~~~~~~~

The phrase no matching function for call to 'max' means the two arguments have different types. The fix is to cast one side, or to make both long long. The program in this lesson makes both long long, and the vector holds long long values.

Using indexes that do not match the restart

In the start-and-end version, the start must be set when the block restarts, not when the best is recorded. A common bug sets bestStart to curStart correctly, but forgets to update curStart when the block restarts. The printed range is then too early or too late, although the sum is right. Check both numbers in the output, not only the sum.

Confusing contiguous with any subset

Kadane's algorithm works only on contiguous blocks. If the question allows you to skip values and take any subset, the answer is different: you take every positive value. Read the word "contiguous" in the statement, and if it is missing, ask.

An empty array

If n is 0, a[0] reads an element that does not exist. The safe check is if (n == 0) before the loop. Some problems say the array is never empty. Read the constraints, and when they are unclear, add the check.

Debugging walkthrough: the restart that loses the start

A student writes the start-and-end version and gets the sum right but the range wrong for the input -2 1 -3 4 -1 2 1 -5 4. The output is sum 6 from index 0 to 6, which claims the block starts at the first value. The true block starts at index 3.

The debugging method is to trace the starts. The student's code restarts cur correctly at index 1 and at index 3, so cur is right. But the line that sets curStart is missing from the restart branch. So curStart stays at 0 all the way through. When cur reaches 6 at index 6, the program records bestStart as curStart, which is still 0. The sum is correct because cur is correct, and the range is wrong because the start was never moved.

The fix is the line curStart = i; inside the if (cur < 0) branch, which the program in this lesson has. The general lesson is that a value you track alongside the main answer needs its own update rule. Every time the algorithm changes the block, it must change the start too. Writing the update next to the restart, in the same branch, makes the pairing hard to forget.

The second lesson is about testing. A sum-only test does not catch this bug, because the sum is correct. Add a range check to your tests, and print both numbers, so that any change to the start is visible at once.

Variations and extensions

The circular array. Suppose the array wraps around, so the last value is next to the first. The best block might cross the seam. The standard answer takes the larger of two numbers: the normal Kadane answer, and the total minus the smallest block sum. There is one exception. If every value is negative, the total minus the smallest block is 0, which is an empty block, so the answer must be the normal Kadane result. Interviewers ask this as a follow-up, so know the rule and the exception.

Maximum product. Replace the sum with a product, and the rule changes. A negative times a negative is positive, so the program must track both the largest and the smallest product ending here. The idea is the same: a pair of running values, updated from the previous pair.

Two-dimensional maximum rectangle. For a grid of numbers, fix a pair of rows, sum each column between them, and run Kadane on the resulting one-dimensional array. This is O(rows squared times columns), and it is a good example of building a hard problem out of an easy one.

Stock profit with one buy and one sell. The best profit from buying on one day and selling on a later day is the largest sum of a block of daily changes. Take the difference between each day and the day before, then run Kadane on those differences. The block of changes that sums largest is the buy and sell window. This is a classic interview reframing, and it is worth remembering.

Interview-style questions and answers

Question: find the maximum sum of a contiguous subarray. Kadane's algorithm: one pass, cur and best, O(n) time and O(1) extra space. Explain the restart rule in one sentence. Mention that the answer must use at least one element.

Question: what if the array is all negative? The answer is the largest single value. Starting from a[0] gives it. Starting from 0 gives the wrong answer, and saying so shows you understand the edge case.

Question: return the indexes of the best block. Track the start of the current block and update it at each restart, then record the start and end when best improves. O(n) time and O(1) extra space.

Question: find the best window of exactly k values. A sliding window, O(n) time and O(1) extra space. Name the difference from Kadane, which allows any length.

When you answer, say the pattern name first, then the rule in one sentence, then the time and space. That order gives the interviewer a clear picture within the first ten seconds.

Real-world uses

Kadane's algorithm is used wherever a program needs to find the most profitable or most intense stretch of a sequence. A trading tool finds the best window to hold a stock from its daily changes. A monitoring system finds the period with the largest rise in errors. A sports app finds the best run of consecutive days with a training load above a threshold. Signal processing uses the same idea to find the strongest burst in a recording. In each case the input is a long sequence, the question is about a contiguous part, and the one-pass rule keeps the answer fast enough for live data.

Practice

Try each exercise before you open the solution. Use the Run box to check your work. The first three are easy, the next four are medium, and the last is harder.

1. For the array 5, -2, 3, print the maximum subarray sum using Kadane's rule. The answer is 6, from the whole array.

2. For the array -4, -1, -7, print the maximum subarray sum. The answer is -1.

3. Modify the start-and-end program to print none when all values are negative. Test with 3 followed by -1 -4 -2.

4. Read n and the values, and print the largest sum of any non-empty block that has an even length. Test with 4 followed by 1 2 3 4. The even-length blocks are 1 2 (sum 3), 2 3 (5), 3 4 (7), and 1 2 3 4 (10). The answer is 10.

5. Read the daily prices of a stock and print the largest profit from one buy and one sell, with the buy day before the sell day. Test with 6 followed by 7 1 5 3 6 4. The answer is 5, from buying at 1 and selling at 6.

6. Write a program that reads n, k and the values, and prints the largest sum of any window of k values. This is the sliding window from this lesson. Test with 5 2 and 1 9 2 8 3. The answer is 11.

7. Explain in two sentences why cur = max(a[i], cur + a[i]) is the same as "restart when cur is negative".

8. Print the maximum subarray sum of the array 1, -1, 1, -1, 1, -1, 1, and also the start and end of the best block. The answer is 1, and the block can be the first value alone, from index 0 to 0.

9. A student writes long long best = a[0]; and int cur = a[0];, and gets a compile error on the max call. Explain the error and fix it in one line.

10. Explain why Kadane's algorithm uses O(1) extra space, and say what the table in the lesson would need to store if you kept all the values.

What you now know

• The maximum subarray sum is the largest total of any contiguous block, and Kadane's algorithm finds it in one O(n) pass.
• The rule is cur = max(a[i], cur + a[i]) and best = max(best, cur). Keep the running total only while it helps, and restart it when it hurts.
• Start cur and best at the first element, not at 0, so that all-negative arrays give the right answer.
• Tracking the start and end of the block needs its own updates, made in the same place as the restart.
• Use long long for the running values, and keep both sides of a max call the same type.
• A window of fixed length uses a sliding window instead, and the wording of the problem tells you which tool to pick.