Maximum Subarray in Java DSA: From Brute Force to Kadane’s Algorithm

Learn Maximum Subarray in Java DSA step by step — from brute force to Kadane’s algorithm, with full dry runs on an 8-element array and clean, beginner-friendly code.

1. Introduction

Maximum Subarray in Java is a problem that looks tricky but hides a beautiful trick. You get an array of numbers, some positive and some negative. Your job is to find the run of numbers, sitting next to each other, that adds up to the biggest total.

The word that matters here is contiguous. The numbers must touch. You cannot cherry-pick the good ones and skip the bad ones in the middle. Once you start a run, the negatives inside it come along too.

We will build the answer in three steps, like always. Brute force tries every possible run with nested loops. A cleaner version keeps a running sum so it stops recomputing the same thing. The last one, Kadane’s algorithm, walks the array once and decides at each number whether to keep going or start fresh.

Every approach gets a full dry run on the same eight numbers. No step is skipped, so you can watch each variable change, line by line, and see exactly why the answer comes out to 6.

2. Understanding the Problem

Let us nail down the rules before we touch any code.

• You get an array of integers, like [-2, 1, -3, 4, -1, 2, 1, -5].
• Pick a run of numbers that sit side by side.
• That run must add up to the largest possible sum.
• Return only that sum, not the run itself, for the classic version.

For our array the best run is [4, -1, 2, 1], and it adds up to 6. Notice it even includes a negative, the -1. We keep it because dropping it would break the run, and the numbers around it are worth more than the -1 costs.

One more thing. The array can be all negative, like [-3, -1, -2]. Then the answer is just the single largest number, here -1. A good solution must handle that without returning zero.

3. Concepts You Need Here

3.1 A Running Sum

A running sum is just a total you carry as you walk the array. You add each new number to it as you pass. This saves you from adding the same stretch of numbers over and over.

3.2 Extend or Restart

This is the heart of Kadane’s algorithm. At each number you face one choice. Do you glue this number onto the run you already have, or do you throw that run away and start a brand new run right here?

• If the run so far is still helping, keep it and add the new number.
• If the run so far has gone negative, it only drags you down, so drop it and start fresh at the current number.

That single decision, made once per number, is why Kadane’s runs in one clean pass.

4. Approach 1: Brute Force

Try every possible run. For each starting point, stretch the run out to every ending point, add the numbers up, and keep the biggest total you ever see. It is slow, but it makes the goal crystal clear.

4.1 Pseudocode

best = -infinity
 
for start from 0 to n-1:
    for end from start to n-1:
        sum = 0
        for k from start to end:     // add the run from scratch
            sum = sum + nums[k]
        if sum > best:
            best = sum
 
return best

4.2 Pseudocode Explained

• The outer loop picks where a run starts.
• Its middle loop picks where that run ends.
• A third, inner loop adds up the run from start to end, fresh each time.
• Whenever a run beats the record, we save its sum in best.

4.3 Java Code

public class MaxSubarrayBrute {
 
    public static int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
 
        for (int start = 0; start < nums.length; start++) {
            for (int end = start; end < nums.length; end++) {
                int sum = 0;
                for (int k = start; k <= end; k++) {
                    sum += nums[k];
                }
                if (sum > best) {
                    best = sum;
                }
            }
        }
        return best;
    }
 
    public static void main(String[] args) {
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5 };
        System.out.println(maxSubArray(nums)); // 6
    }
}

4.4 Java Code Explained

• Line 4 sets best to the smallest possible int, so any real run beats it.
• Then line 6 starts the outer loop that picks where a run begins.
• Line 7 runs the middle loop that picks where the run ends.
• Lines 8 to 11 are the inner loop, which rebuilds the run’s sum from scratch.
• On a new record, lines 12 to 14 update best.
• Finally, line 17 returns the largest sum found.

4.5 Dry Run of the Brute Force

Array: [-2, 1, -3, 4, -1, 2, 1, -5]. We trace every start value and every end value, so all 36 runs are shown. Watch the sum column and the best column together.

Legend: start is the left end of the run, end is the right end, sum is the total of nums[start..end], and best is the largest sum seen so far.

Pass start = 0

Then start = 1

Next start = 2

Winning pass, start = 3

Passes start = 4 to 7

4.6 Reading the Dry Run

Let us walk the trace start by start and watch best climb.

Pass start = 0.

Here the run always begins at -2, so it carries a handicap from the very first number.

• At end = 0 the run is just [-2], sum -2. That beats negative infinity, so best becomes -2.
• By end = 1 we add 1 and the sum climbs to -1, a new record.
• Then end = 2 adds -3 and the sum drops to -4, so nothing changes.
• Near the end, at end = 6, the sum reaches 2, the best this pass can offer before the -5 spoils it.

Next, start = 1.

Now we drop the leading -2 and start fresh at 1. This helps a lot.

• Runs stay small until end = 5, where the sum hits 3 and sets a record.
• Adding the next 1 at end = 6 pushes the sum to 4, another record.
• Finally the -5 at end = 7 drags the sum down to -1, so best holds at 4.

Then start = 2.

This run opens on -3, a deep hole. It never digs out.

• The best it reaches is 3, back at end = 6, which only ties the old record.
• Because a tie is not a new record, best stays at 4 the whole pass.

Now start = 3.

Here is the winning pass. It starts right on the 4.

• At end = 3 the run is just [4], sum 4.
• Then end = 5 brings the sum to 5, a fresh record.
• Next, end = 6 adds 1 and the sum reaches 6, the true answer.
• After that the -5 knocks it back to 1, so best locks in at 6.

Passes start = 4 to 7.

These late runs are short and start too far right to beat 6.

• The strongest is [2, 1] with sum 3, well under the record.
• Every one of these leaves best untouched at 6.

So 36 runs were checked in all, yet the winner was found back in the start = 3 pass. The brute force has no way to skip ahead, so it grinds through them anyway.

4.7 Time and Space Cost

• Time is O(n³), because the inner loop rebuilds each run’s sum from scratch.
• Space is O(1), since we only track best and a few counters.

For eight numbers this is fine. For a few thousand it crawls, which is why we tighten it next.

5. Approach 2: Two Loops with a Running Sum

The brute force wastes time re-adding the same numbers. We can fix that. Keep one run open and extend its sum by a single addition as the end moves right. That drops the third loop entirely.

5.1 Pseudocode

best = -infinity
 
for start from 0 to n-1:
    sum = 0
    for end from start to n-1:
        sum = sum + nums[end]    // extend, no rebuild
        if sum > best:
            best = sum
 
return best

5.2 Pseudocode Explained

• The outer loop still fixes where the run starts.
• sum resets to 0 each time a new start begins.
• As end slides right, we add just one number to sum.
• Any time sum beats best, we save it.

5.3 Java Code

public class MaxSubarrayRunningSum {
 
    public static int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
 
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum > best) {
                    best = sum;
                }
            }
        }
        return best;
    }
 
    public static void main(String[] args) {
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5 };
        System.out.println(maxSubArray(nums)); // 6
    }
}

5.4 Java Code Explained

• Line 4 sets best to the smallest int again.
• Then line 6 starts the outer loop; line 7 resets sum to 0 for each new start.
• Line 8 runs the inner loop as end slides right.
• Line 9 extends the run with sum += nums[end], one number only.
• Lines 10 to 12 save the sum whenever it sets a new record.

5.5 Dry Run of the Running Sum

Array: [-2, 1, -3, 4, -1, 2, 1, -5]. This time each row is one extension of the run, so sum grows by exactly one number per step. We trace every start pass fully.

Legend: sum before is the running total from the previous step, +nums[end] is the number just added, sum after is the new total, and best is the record so far.

Pass start = 0, sum reset to 0

Then start = 1, sum reset to 0

Next start = 2, sum reset to 0

Winning pass, start = 3, sum reset to 0

Passes start = 4 to 7

5.6 Reading the Dry Run

The answer matches the brute force exactly. What changed is speed, not results. Watch how sum only ever moves by one addition.

Pass start = 0.

• Here sum begins at 0, then -2 pulls it to -2 and sets the first record.
• Adding 1 lifts it to -1, another record.
• From there the -3 drops it to -4, but the 4 later recovers it to 0.
• By end = 6 the sum reaches 2, the peak for this start.

Next, start = 1.

• sum resets, then climbs slowly as we add 1, drop with -3, and recover with 4.
• At end = 5 it reaches 3 and beats the old best.
• One step later, at end = 6, the extra 1 makes it 4, the new record.

Then start = 2.

• This run opens on -3, so it spends the whole pass climbing out of a hole.
• Its high point is 3, which only ties, so best stays at 4.

Now start = 3.

• sum starts with 4 straight away, a strong opening.
• The dip at -1 softens it to 3, but the 2 pushes it to 5, a record.
• Then the 1 makes it 6, the final answer, before -5 spoils the rest.

Passes start = 4 to 7.

• These short tails never reach 6, so best is already settled.

Every value here matches the brute force column for column. We simply stopped rebuilding the sum, so each row is one cheap addition instead of a fresh loop.

5.7 Time and Space Cost

• Time is O(n²), because two loops replace the old three.
• Space is O(1), the same handful of variables.

A solid jump over brute force. Still, we visit the same pairs many times, and interviewers usually want the single-pass version next.

6. Approach 3: Kadane’s Algorithm

Kadane’s algorithm walks the array once. At each number it makes the extend-or-restart choice. It keeps a running sum for the current run and a separate best for the largest run ever seen.

The trick is this. If the running sum ever goes negative, it can only hurt what comes after, so we throw it away and start again at the current number.

6.1 Pseudocode

best = nums[0]
cur  = nums[0]
 
for i from 1 to n-1:
    // extend the old run, or restart at nums[i]
    cur  = max(nums[i], cur + nums[i])
    best = max(best, cur)
 
return best

6.2 Pseudocode Explained

• cur is the best run that ends exactly at the current number.
• max(nums[i], cur + nums[i]) is the extend-or-restart choice in one line.
• best remembers the largest cur we have ever reached.
• Starting both at nums[0] handles all-negative arrays cleanly.

6.3 Java Code

public class MaxSubarrayKadane {
 
    public static int maxSubArray(int[] nums) {
        int best = nums[0];
        int cur = nums[0];
 
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
 
    public static void main(String[] args) {
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5 };
        System.out.println(maxSubArray(nums)); // 6
    }
}

6.4 Java Code Explained

• Lines 4 and 5 seed both best and cur with nums[0], not zero.
• Then line 7 starts the loop at index 1, since index 0 is the seed.
• Line 8 is the extend-or-restart choice, Math.max(nums[i], cur + nums[i]).
• Line 9 lifts best with Math.max(best, cur) whenever cur climbs higher.
• Finally, line 11 returns best.

6.5 Dry Run of Kadane’s Algorithm

Array: [-2, 1, -3, 4, -1, 2, 1, -5]. We seed both cur and best with nums[0] = -2, then trace every index from 1 to 7. Each row shows the extend value, the restart value, which one wins, and the new best.

Legend: extend = cur + nums[i] (glue onto the old run), restart = nums[i] (start fresh here), cur = the winner of those two, best = largest cur so far.

6.6 Reading the Dry Run

This is the whole algorithm in eight rows. Let us take each index and see why the winner was chosen.

Seed: cur = -2, best = -2.

We start the run on the only number available, -2. There is nothing to compare yet, so both cur and best just hold -2.

At index 1, nums[i] = 1.

• Extend gives cur + 1 = -2 + 1 = -1.
• Restart gives just 1.
• Since 1 beats -1, we restart. The old -2 run was dead weight, so we drop it.
• cur is now 1, and best rises to 1.

Now index 2, nums[i] = -3.

• Extend gives 1 + (-3) = -2.
• Restart gives -3.
• Here -2 is larger than -3, so we extend. Odd as it feels, keeping the run loses less than starting over.
• cur drops to -2, but best stays at 1.

Then index 3, nums[i] = 4.

• Extend gives -2 + 4 = 2.
• Restart gives 4.
• Because 4 beats 2, we restart. The negative -2 prefix was only holding us back.
• cur jumps to 4, and best climbs to 4. This is where the winning run begins.

At index 4, nums[i] = -1.

• Extend gives 4 + (-1) = 3.
• Restart gives -1.
• Now 3 beats -1, so we extend and swallow the -1.
• cur is 3, best holds at 4. We accept a small dip because the run is still positive.

Now index 5, nums[i] = 2.

• Extend gives 3 + 2 = 5.
• Restart gives 2.
• Since 5 beats 2, we extend. The run keeps paying off.
• cur is 5, and best rises to 5.

Then index 6, nums[i] = 1.

• Extend gives 5 + 1 = 6.
• Restart gives 1.
• Again extend wins, so cur reaches 6.
• best climbs to 6, the true answer. The run is now [4, -1, 2, 1].

Finally index 7, nums[i] = -5.

• Extend gives 6 + (-5) = 1.
• Restart gives -5.
• Extend still wins at 1, so cur becomes 1.
• That is below 6, so best stays at 6 and the loop ends.

One pass, one decision per number, and the answer falls out as 6. Notice best only ever moves up and never resets. It quietly records the high-water mark while cur does the day-to-day work.

6.7 Comparing the Three Traces

7. The Dry Run on Paper

Tables are exact, but a sketch often clicks faster. Here is the same Kadane trace drawn by hand.

• A green box marks each step where best moves up to a new record.
• A gold box marks a restart, where the old run is thrown away.
• At the bottom the final answer reads 6, from the run [4, -1, 2, 1].

8. Comparing the Three Approaches

All three return the same 6. They just pay different prices to get there.

The gap here is time, not memory. All three use O(1) extra space, yet Kadane’s finishes in a single walk while the others revisit the same stretches again and again.

In an interview, open with brute force, point out the wasted inner loop, tighten it to the running sum, then land on Kadane’s and explain the extend-or-restart rule. That climb is the story interviewers want to hear.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on Maximum Subarray. Keep them close.

• Seeding best or cur with 0 breaks all-negative arrays, which should return the largest single number.
• Resetting cur to 0 instead of nums[i] on a restart quietly changes the logic and hides negatives.
• Forgetting to update best after cur can miss a peak that appears mid-array.
• An array with one element, like [5], should simply return that element.
• Confusing this with a subsequence problem is common; here the numbers must be contiguous.

Run the all-negative case and the single-element case through your code before you call it done. They catch more bugs than any friendly input will.

10. Interview Questions

11. Conclusion

Maximum Subarray in Java looks scary with its mix of positives and negatives. But once you spot the extend-or-restart idea, the fear melts away.

Our eight-number trace showed the payoff clearly. Brute force ground through all 36 runs. The running sum trimmed the wasted adds. Kadane’s made one clean pass and still landed on 6.

So take the pattern, not just the answer. Carry a running total. Ask at each step whether the past is helping or hurting. Then drop it the moment it turns negative.

That habit turns a slow O(n³) grind into a single O(n) walk. It will do the same for many array problems waiting further down the list.

12. Further Reading

• LeetCode Maximum Subarray problem — practice the original and submit your own solution.
• Oracle Java Math documentation — the official reference for Math.max and other helpers used here.
• Previous in this series: Contains Duplicate in Java — use a hash set to spot a repeat in one pass.
• Next in this series: Move Zeroes in Java — push all zeroes to the end with a two-pointer sweep.

javahandson.com | DSA Series | Arrays & Strings