Maximum Subarray Sum (Kadane Algorithm)

Table of Contents +

This is a famous array question. It looks simple. But the interviewer is not just asking for a sum. They want to see if you can solve it in one pass, without checking every possible piece of the array.

📈 The Problem

You are given an array of numbers. Some are positive. Some are negative. You have to find the contiguous part of the array that adds up to the biggest total. Contiguous means the elements sit next to each other. You cannot skip around and pick whatever you like.

Here is what that looks like:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

That 6 comes from the piece [4, -1, 2, 1]. Add those up and you get 6. No other run of neighbours beats it. So the answer is the sum, which is 6.

🧠 The Simple Idea First

Before the smart way, let’s think about the obvious way. You could try every possible subarray. Pick a start point. Then try every end point after it. Add up the numbers in between. Keep track of the biggest total you have seen.

That works. But look at the cost. For each start you walk to every end. And for each of those you add up the middle. So the time grows fast. That is O(n^2) at best, and O(n^3) if you re-add the middle every time. On a big array this is too slow. So this is the version to mention, then improve.

⚡ Kadane’s Algorithm

Here is the trick interviewers want. It is called Kadane’s algorithm. The whole idea is one running sum that we carry as we walk through the array once.

We keep two numbers:

  • currentSum is the best sum of a piece that ends right here at the current element.
  • bestSum is the best sum we have seen anywhere so far.

Now think about the key question at each step. As you stand on a new number, should you add it to the run you already have? Or should you throw that run away and start fresh from here?

The answer is simple. If the run you carried so far is negative, it is only dragging you down. A negative running total does not help any future element. So you drop it and start a new run from the current number. But if the run so far is positive, it gives you a head start. So you keep it and add the current number.

Think of it like walking and collecting coins. If your bag already has debt in it, you throw the bag away and start with an empty one. If your bag has money, you keep it and add the new coin.

Negative numbers are the whole trick

The reason this problem is interesting is the negative numbers. If every number were positive, the answer would just be the sum of the entire array. The negatives are what force you to decide when to cut your run and start over.

Steps to find the maximum subarray sum

Let’s write the steps down before any code.

  1. Set both currentSum and bestSum to the first element of the array.
  2. Walk from the second element to the end. For each element:
    • If currentSum is less than 0, reset currentSum to the current element. Otherwise add the current element to currentSum.
    • If currentSum is greater than bestSum, update bestSum.
  3. When the walk is done, bestSum holds the largest subarray sum.

Let’s trace it on [-2, 1, -3, 4, -1, 2, 1, -5, 4] so you can see it happen:

Start:  currentSum = -2,  bestSum = -2
 1  ->  currentSum was negative, restart -> currentSum = 1,  bestSum = 1
-3  ->  add -3 -> currentSum = -2,            bestSum = 1
 4  ->  currentSum was negative, restart -> currentSum = 4,  bestSum = 4
-1  ->  add -1 -> currentSum = 3,             bestSum = 4
 2  ->  add  2 -> currentSum = 5,             bestSum = 5
 1  ->  add  1 -> currentSum = 6,             bestSum = 6
-5  ->  add -5 -> currentSum = 1,             bestSum = 6
 4  ->  add  4 -> currentSum = 5,             bestSum = 6
Answer: 6

Code for Kadane’s algorithm

Now let’s see it in every language.

max_subarray_sum.py
# function to find the maximum subarray sum (Kadane's algorithm)
def max_subarray_sum(arr):
    current_sum = arr[0]
    best_sum = arr[0]


    # walk through the rest of the array once
    for i in range(1, len(arr)):
        # drop a negative run, otherwise keep adding
        if current_sum < 0:
            current_sum = arr[i]
        else:
            current_sum = current_sum + arr[i]


        # remember the best sum seen so far
        if current_sum > best_sum:
            best_sum = current_sum


    return best_sum


def main():
    arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print("Maximum subarray sum:", max_subarray_sum(arr))


if __name__ == "__main__":
    main()

The output of the above code will be:

Maximum subarray sum: 6

⏱️ Time and Space Complexity

Approach Time Space
Check all subarrays (brute force) O(n^2) O(1)
Kadane’s algorithm (one pass) O(n) O(1)

The brute force way checks every start with every end. So the time grows as O(n^2). Kadane walks the array a single time. So it is O(n) time. Both use only a couple of variables. So both are O(1) extra space. The big win here is speed. That O(n) one-pass solution is the answer the interviewer is hoping for.

Watch out for all-negative arrays

If every number in the array is negative, the answer is the single largest number, not 0. Starting both currentSum and bestSum at the first element handles this for you. Be careful with versions that start bestSum at 0. They wrongly return 0 for an all-negative input.

🧩 Key Takeaways

  • ✅ Maximum subarray sum asks for the largest total from a contiguous run of elements.
  • ✅ The brute force way checks all subarrays and is O(n^2). Kadane does it in one pass at O(n).
  • ✅ Carry a running currentSum. If it ever goes negative, drop it and start fresh from the current element.
  • ✅ Start currentSum and bestSum at the first element so all-negative arrays still work.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does 'contiguous subarray' mean in this problem?

    Why: Contiguous means the chosen elements are neighbours in the array; you cannot skip around and pick whatever you like.

  2. 2

    In Kadane's algorithm, when do you throw away the running sum and start fresh?

    Why: A negative running sum only drags future elements down, so you drop it and restart from the current element.

  3. 3

    What is the time complexity of Kadane's algorithm?

    Why: Kadane walks through the array a single time, so it runs in O(n) time with O(1) extra space.

  4. 4

    For an array where every number is negative, what should the answer be?

    Why: With all negatives, the best contiguous run is just the single largest element, which is why we start bestSum at the first element instead of 0.

Score: 0 / 4

🚀 What’s Next?

Now that you have Kadane’s running-sum idea, try these next:

Kadane’s algorithm is one of those patterns that feels like magic the first time and obvious the tenth time. Trace it on a few arrays by hand and the running-sum idea will stick.

Previous Find the Missing Number Next Two Sum

Share & Connect

Share on LinkedIn