Maximum Subarray - Kadane's Algorithm

Maximum Subarray - Kadane's Algorithm is is a classic problem that introduces one of the most elegant uses of dynamic programming. It teaches you how to keep track of optimal sub-solutions and make decisions based on current and previous results. Once you’ve got this down, it opens the door to more complex dynamic programming challenges.

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]  
Output: 6  
Explanation: [4,-1,2,1] has the largest sum = 6

1. Clarify Requirements Before Jumping Into Code

We are given an array of integers that may include negative values. We need to return the maximum possible sum from a contiguous subarray. That means the elements must be next to each other — we can't skip around.

We’re not asked to return the subarray itself (just the sum), although we can modify our approach to return it later if needed.

2. Identify the Category of the Question

This is a Dynamic Programming (DP) problem.

It also has elements of Greedy thinking because we constantly decide: "Do I continue the current subarray, or start fresh from here?"

It’s commonly solved with Kadane’s Algorithm, a linear time dynamic programming approach.

3. Consider a Brute‑Force Approach to Understand the Problem

For the brute-force solution, we would try all possible subarrays and compute their sums:

• For every i, try every subarray ending at j ≥ i

• Sum up each and keep track of the max

This is O(n²). Not great for large arrays, but it helps understand that to optimize, we're likely going to be looking for opportunities to reuse work instead of doing a bunch of repeat calculations.

4. Brainstorm More Solutions

If all the elements in my input array are positive, then question is trivial: obviously the best solution is to sum all of the elements.

Things get more complicated through when we recognize that my input can have negative numbers. Why? Because at any point, I could hit a negative number that's so large that it doesn't make sense to include it in my final sum. But on the flip side, the negative number could be small enough that it's effect on the final sum is overcome by the elements on either side of it, meaning we should include it in the final sum. So how do we know whether to include an element in our final sum or not?

Let's start at the beginning: as I am iterating through each an element in the array, what are my choices? I essentially have two:

1. I can add the current element to my current "best possible subarray", or

2. I can start a new subarray from my current element

But that begs the question: when does it make sense to start a new subarray? It really only makes sense to start a new subarray if doing so gives me a better start to my "best possible subarray" than I could get if I were to continue building on the previous one.

For example:

-4, -3, -3, 5, 6, 7 ...

Here, the best I can achieve from the first three elements in the array is -3.

But, then I find that the fourth element is a positive number. Obviously it makes sense to start my result from scratch with element four, because there's no way that including the first three elements is going to lead to a larger sum.

But what if, for example, I am able to get a better sum if I just skip one of the elements? For example:

-3, 10, -4, 5, 6, 7 ...

Here it makes sense to start my best possible subarray from element two, because it is so large that it overcomes the negative value in element 3.

What this means is that when I'm deciding whether or not to start a new subarray, I'm not just looking to compare against the sum of all previous elements, I'm trying to compare against the best possible sum of all previous subarrays.

And if I had to keep track of the exact elements that were contributing to that best possible subarray, this nuance could lead to a fair bit of complexity. But I'm not! I'm just looking for the sum of the best possible subarray.

Which means, I don't need to keep track of the exact subarrays themselves, I only need to keep track of the best possible sum that I've been able to accomplish so far. Then, as I iterate through the array, all I have to do is decide: does adding the next element lead to a better sum, or does it make more sense to start over with a new subarray?

How do I translate that into code?

We can start by defining a couple of variables:

• currSum: the best subarray sum ending at the current index, which every step is updated to:

  • my previous best possible sum plus the current element: currSum + nums[i] (i.e. because it makes more sense to extend the previous subarray)

  • or, it's nums[i] (because I want to start a new subarray).

• maxSum: the best subarray sum seen so far. This is my result

And since at each step I'm simply picking the larger numbers, this translate to:

• On each iteration:

  • currSum = max(nums[i], currSum + nums[i])

  • maxSum = max(maxSum, currSum)

This is Kadane's algorithm!

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute-force	O(n²)	O(1)	Simple to implement	Too slow for large inputs
Kadane’s Algorithm	O(n)	O(1)	Fast, elegant, minimal space	Doesn’t track indices unless extended

6. Write Pseudocode to Structure Your Thoughts

Initialize currSum = nums[0]
Initialize maxSum = nums[0]

Loop from i = 1 to end of array:
    currSum = max(nums[i], currSum + nums[i])
    maxSum = max(maxSum, currSum)

Return maxSum

7. Consider Edge Cases

• All numbers negative → We still need to return the least negative number (not 0).

• One element → Should return that number

• Mixed positive and negative → Should correctly identify the optimal subarray

8. Write Full Code Syntax

public class MaximumSubarray {

    public int maxSubArray(int[] nums) {
        int currSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }

        return maxSum;
    }
}

9. Test Your Code

public static void main(String[] args) {
    MaximumSubarray solver = new MaximumSubarray();

    System.out.println(solver.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));  // 6
    System.out.println(solver.maxSubArray(new int[]{1}));                     // 1
    System.out.println(solver.maxSubArray(new int[]{5,4,-1,7,8}));            // 23
    System.out.println(solver.maxSubArray(new int[]{-1,-2,-3,-4}));           // -1
    System.out.println(solver.maxSubArray(new int[]{0,0,0,0}));               // 0
}

10. Key Lessons to Remember for Future Questions

• Kadane’s Algorithm is a gold standard for 1D subarray sum problems.

• Your instinct when you first see this question might be to overcomplicate the problem by trying to keep track of the exact indices of the best possible subarray. Kadane's Algorithm works on the insight that you don't need to track the exact indices of the best possible summary, just the sum!

• So, always remember to take a close look at the question and making sure not to overcomplicate things by trying to do more than the question requires.

• This technique generalizes into 2D subarrays (with more complexity).

• Practice this pattern — it reappears in stock problems, DP matrix traversal, etc.

• A version of this can also track the actual subarray by storing start and end indices when the currSum resets or improves.

Good Luck and Happy Coding!