Maximum Subarray Sum in Java: Solution, Explanation & Practice

Find the maximum sum of a contiguous subarray

Problem summary

Write a program that finds the maximum sum of any contiguous subarray (Kadane's algorithm).

Starter code

public class Main {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // Test case 1
        
        // Find max subarray sum
        // Print: Max sum: <result>
    }
}

Expected output and test cases

[4,-1,2,1] = 6
```
Max sum: 6
```
All positive sums
```
Max sum: 5
```
All negative, pick largest
```
Max sum: -1
```

Hints

Kadane's: track current sum and max sum
Reset current sum if it goes negative
Update max whenever current exceeds it

Validated solution

Reveal Java solution

public class Main {
    static int maxSubarraySum(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: " + maxSubarraySum(new int[] {4, -1, 2, 1, -5, 4}));
    }
}

How to approach the problem

Kadane’s algorithm asks whether extending the previous subarray is better than starting fresh at the current value. Keep the best sum ending here and the best sum seen anywhere as separate pieces of state.

Approach

Seed both values from the first element.
Choose between restart and extension at every position.
Update the global best after the local decision.

Time and space complexity

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

Edge cases to test

All-negative input must return its least-negative element.
An empty array needs a separate contract before reading values[0].

Common mistakes

Starting both sums at zero and incorrectly returning zero for all-negative input.
Confusing a contiguous subarray with an arbitrary subset.

Follow-up challenge

Track the start and end indices of the best subarray too.

Related Arrays exercises

Practice all Arrays exercises · Run this idea in the Java compiler