Find Maximum Subarray Sum (Kadane's Algorithm) in Java
Problem
The maximum subarray sum is the largest possible sum of any contiguous run of elements within the array — including the possibility that a single element is the best choice on its own.
Given an array of integers, find the largest sum achievable by any contiguous subarray.
Java Program
public class MaxSubarraySumBrute {
public static void main(String[] args) {
int[] arr = {-2, 4, -1, 3, -5, 2, 6, -3};
int maxSum = arr[0];
for (int i = 0; i < arr.length; i++) {
int sum = 0; // reset for each new starting index
for (int j = i; j < arr.length; j++) {
sum += arr[j]; // extend the subarray by one element
if (sum > maxSum) maxSum = sum;
}
}
System.out.println("Maximum subarray sum: " + maxSum);
}
}Output
Core Logic
Computing the sum of every possible contiguous subarray directly, and keeping track of the largest one seen, checks every candidate explicitly.
- 1The outer loop picks a starting index
ifor a candidate subarray. - 2The inner loop extends the subarray one element at a time, adding
arr[j]to a runningsum. - 3After each extension,
sumis compared againstmaxSum, updating it whenever a larger total is found. - 4By the time both loops finish, every one of the array's contiguous subarrays has had its sum checked.
[-2, 4, -1, 3, -5, 2, 6, -3], the subarray [4, -1, 3, -5, 2, 6] sums to 9, the largest total found across every subarray tried.Key Point: Every one of the O(n²) possible subarrays is checked explicitly, which is easy to follow but wasteful — a single pass can answer the same question.
Why: Every possible subarray's sum is computed directly by extending the inner loop's running total, so the nested loops do O(n²) work with no extra memory.
Key Concepts
Approach 2: Kadane's Algorithm
public class MaxSubarraySumKadane {
public static void main(String[] args) {
int[] arr = {-2, 4, -1, 3, -5, 2, 6, -3};
int maxEndingHere = arr[0];
int maxSoFar = arr[0];
for (int i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); // extend, or restart from here
maxSoFar = Math.max(maxSoFar, maxEndingHere); // best subarray ending anywhere so far
}
System.out.println("Maximum subarray sum: " + maxSoFar);
}
}
Output
Core Logic
At each position, deciding whether to extend the previous running subarray or start a fresh one right there — and always taking whichever gives the bigger sum — turns out to find the global maximum in a single pass.
- 1
maxEndingHeretracks the best sum of a subarray that ends exactly at the current position. - 2
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i])decides, at each step, whether extending the previous subarray still beats starting over fromarr[i]alone. - 3
maxSoFartracks the bestmaxEndingHereseen across the whole scan, updated after every step. - 4By the end of one pass,
maxSoFarholds the answer — no nested loop was ever needed.
[-2, 4, -1, 3, -5, 2, 6, -3], maxEndingHere resets to 4 after the leading -2 drags it down, then keeps extending through -1, 3, -5, 2, 6 to reach 9, which becomes maxSoFar.Key Point: The local, greedy choice at each position — extend or restart — provably leads to the global maximum, which is the key insight that makes Kadane's algorithm work: it never needs to look back and reconsider an earlier decision.
Why: Each element is visited exactly once, deciding whether to extend the running subarray or start fresh from the current element — no nested loop and no extra memory beyond two running variables.