Maximum Subarray (Kadane's Algorithm) in Java: 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

Related Data Structures & Algorithms exercises

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