Maximum Subarray (Kadane's Algorithm) in Java: Solution, Explanation & Practice

Find contiguous subarray with largest sum

Problem summary

Given an array, find the contiguous subarray with the largest sum. Kadane's algorithm solves this in O(n).

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        
        // currentMax = max(nums[i], currentMax + nums[i])
        // Decide: start fresh or extend current subarray
        // Print: Max sum: 6
    }
}

Expected output and test cases

[-2,1,-3,4,-1,2,1,-5,4] → [4,-1,2,1]
```
Max sum: 6
```
[1] → [1]
```
Max sum: 1
```
[5,4,-1,7,8] → all
```
Max sum: 23
```

Hints

At each position, decide: extend current subarray or start new
currentMax = max(nums[i], currentMax + nums[i])
If currentMax + nums[i] < nums[i], better to start fresh
Track global maximum across all positions

Validated solution

Reveal Java solution

public class Main {
    static int maxSum(int[] values) {
        int best = values[0], endingHere = values[0];
        for (int i = 1; i < values.length; i++) {
            endingHere = Math.max(values[i], endingHere + values[i]);
            best = Math.max(best, endingHere);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println("Max sum: " + maxSum(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}

How to approach the problem

At each position, a maximum-sum subarray ending there either starts fresh or extends the previous candidate. Keeping those two possibilities compressed into endingHere gives a linear-time result.

Approach

Seed from the first value to preserve all-negative answers.
Choose restart or extension locally.
Record the best local result globally.

Time and space complexity

Time: O(n). Space: O(1).

Edge cases to test

A one-element array is its own answer.
All negative values still require selecting one element.

Common mistakes

Resetting negative sums to zero and allowing an empty subarray without saying so.
Using this algorithm for non-contiguous subsequences.

Follow-up challenge

Return the maximum product subarray and explain why two running products are required.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler