In this tutorial, I will demonstrate how to find the maximum subarray sum using Kadane's algorithm in Java. This is a popular array-based coding interview problem that helps you understand dynamic programming, running sums, and algorithm optimization.
The maximum subarray problem asks you to find a contiguous portion of an integer array whose elements have the largest possible sum.
For example, consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The contiguous subarray [4, -1, 2, 1] has a sum of 6, which is the maximum possible sum.
You can solve this problem using nested loops, but that approach takes quadratic time. Kadane's algorithm finds the maximum subarray sum in linear time by maintaining the best sum ending at each position.
In this tutorial, you will learn how Kadane's algorithm works, how to implement it in Java, how to retrieve the actual maximum-sum subarray, and how its performance compares with a brute-force solution.
1. Problem Statement
Given an integer array, find the maximum possible sum of a nonempty contiguous subarray.
A contiguous subarray consists of consecutive elements from the original array.
Example 1
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: Maximum Subarray Sum: 6
Explanation:
The subarray [4, -1, 2, 1] produces the maximum sum:
4 + (-1) + 2 + 1 = 6
Example 2
Input: [1, 2, 3, 4] Output: Maximum Subarray Sum: 10
Since every number is positive, the entire array forms the maximum-sum subarray.
Example 3
Input: [-5, -2, -8, -1, -4] Output: Maximum Subarray Sum: -1
When all numbers are negative, the maximum-sum nonempty subarray contains the largest individual number.
2. What Is Kadane's Algorithm?
Kadane's algorithm is an efficient method for finding the maximum sum of a contiguous subarray.
It processes the array from left to right and maintains two values:
- currentSum: The maximum sum of a nonempty subarray ending at the current index.
- maxSum: The maximum subarray sum found anywhere in the array so far.
At each element, the algorithm makes one important decision:
Should the current element extend the previous subarray, or should a new subarray start at the current element?
This decision is expressed using:
currentSum = max(currentNumber, currentSum + currentNumber) maxSum = max(maxSum, currentSum)
The first expression chooses between starting a new subarray and extending the previous one.
The second expression updates the best overall sum.
This simple technique eliminates the need to examine every possible subarray.
3. Method 1: Maximum Subarray Sum Using Kadane's Algorithm
The following Java program implements Kadane's algorithm using a single loop.
It handles positive numbers, negative numbers, zeros, and arrays containing only negative values.
Java Program
import java.util.Arrays;
public class MaximumSubarraySum {
/**
* Finds the maximum sum of a nonempty
* contiguous subarray using Kadane's algorithm.
*
* @param nums input integer array
* @return maximum subarray sum
*/
public static long maxSubarraySum(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException(
"Array must not be null or empty");
}
long currentSum = nums[0];
long maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// Start a new subarray or extend the current one
currentSum = Math.max(
(long) nums[i],
currentSum + nums[i]
);
// Update the maximum sum
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {
-2, 1, -3, 4, -1, 2, 1, -5, 4
};
long result = maxSubarraySum(nums);
System.out.println("Input Array: "
+ Arrays.toString(nums));
System.out.println("Maximum Subarray Sum: "
+ result);
}
}Output
Input Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Maximum Subarray Sum: 6
Important: The program initializes both sums using the first array element. This ensures that arrays containing only negative numbers are handled correctly.
4. Step-by-Step Explanation of Kadane's Algorithm
Step 1: Validate the Input Array
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException(
"Array must not be null or empty");
}The problem requires a nonempty subarray.
If the array is null or empty, no valid answer exists. Therefore, this implementation throws an IllegalArgumentException.
Step 2: Initialize the Running Sums
long currentSum = nums[0];
long maxSum = nums[0];Both variables are initialized to the first element.
The first element is the only possible nonempty subarray ending at index 0.
Using the first element also ensures the algorithm works correctly when every number is negative.
Step 3: Traverse the Remaining Elements
for (int i = 1; i < nums.length; i++) {The loop starts at index 1 because index 0 was already used to initialize the sums.
Step 4: Decide Whether to Extend or Restart
currentSum = Math.max(
(long) nums[i],
currentSum + nums[i]
);This is the most important step in Kadane's algorithm.
The expression compares two choices:
nums[i]: Start a new subarray at the current element.currentSum + nums[i]: Extend the previous maximum-sum subarray ending at the preceding index.
The algorithm selects whichever choice produces the larger sum.
For example, suppose the previous currentSum is -2 and the current number is 1.
The choices are:
Start new: 1 Extend previous: -2 + 1 = -1 Choose: 1
Starting a new subarray is better because 1 is greater than -1.
Step 5: Update the Maximum Sum
maxSum = Math.max(maxSum, currentSum);After calculating the best sum ending at the current position, the algorithm compares it with the best overall sum.
If the current sum is larger, maxSum is updated.
Step 6: Return the Result
return maxSum;After processing all elements, maxSum contains the largest possible sum of any nonempty contiguous subarray.
5. Dry Run: Kadane's Algorithm
Let's walk through the following input:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Initially:
currentSum = -2 maxSum = -2
For each subsequent number, the algorithm decides whether to start a new subarray or continue the previous one.
| Index | Number | Current Sum | Maximum Sum |
|---|---|---|---|
| 0 | -2 | -2 | -2 |
| 1 | 1 | 1 | 1 |
| 2 | -3 | -2 | 1 |
| 3 | 4 | 4 | 4 |
| 4 | -1 | 3 | 4 |
| 5 | 2 | 5 | 5 |
| 6 | 1 | 6 | 6 |
| 7 | -5 | 1 | 6 |
| 8 | 4 | 5 | 6 |
At index 6, the maximum sum becomes 6.
No later subarray produces a larger sum.
Final result:
Maximum Subarray: [4, -1, 2, 1] Maximum Subarray Sum: 6
6. Method 2: Kadane's Algorithm to Find the Actual Maximum Subarray
The previous program returns only the maximum sum.
In some coding interviews, you may also be asked to return the actual subarray that produces this sum.
You can extend Kadane's algorithm by tracking the starting and ending indexes of the best subarray.
Java Program to Find Maximum Sum and Subarray
import java.util.Arrays;
public class KadaneWithSubarray {
public static void findMaximumSubarray(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException(
"Array must not be null or empty");
}
long currentSum = nums[0];
long maxSum = nums[0];
int start = 0;
int end = 0;
int tempStart = 0;
for (int i = 1; i < nums.length; i++) {
// Decide whether to start a new subarray
if ((long) nums[i] > currentSum + nums[i]) {
currentSum = nums[i];
tempStart = i;
} else {
currentSum += nums[i];
}
// Update the best subarray
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
int[] maxSubarray = Arrays.copyOfRange(
nums, start, end + 1);
System.out.println("Maximum Subarray Sum: "
+ maxSum);
System.out.println("Start Index: " + start);
System.out.println("End Index: " + end);
System.out.println("Maximum Subarray: "
+ Arrays.toString(maxSubarray));
}
public static void main(String[] args) {
int[] nums = {
-2, 1, -3, 4, -1, 2, 1, -5, 4
};
findMaximumSubarray(nums);
}
}Output
Maximum Subarray Sum: 6 Start Index: 3 End Index: 6 Maximum Subarray: [4, -1, 2, 1]
How Subarray Tracking Works
The program maintains three index variables:
tempStart: The starting index of the current candidate subarray.start: The starting index of the best subarray found so far.end: The ending index of the best subarray found so far.
Whenever starting a new subarray is better than extending the previous one, the algorithm updates tempStart.
Whenever currentSum becomes larger than maxSum, it updates the best starting and ending indexes.
The program then extracts the actual subarray using:
Arrays.copyOfRange(nums, start, end + 1);This method returns a new array containing the elements from start through end.
7. Method 3: Maximum Subarray Sum Using Brute Force
The brute-force approach checks all possible contiguous subarrays.
For each starting index, it extends the subarray to the right and maintains the running sum.
Whenever the running sum exceeds the current maximum, the program updates the result.
Java Program Using Nested Loops
import java.util.Arrays;
public class MaximumSubarrayBruteForce {
public static long maxSubarraySum(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException(
"Array must not be null or empty");
}
long maxSum = Long.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
long currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
maxSum = Math.max(
maxSum, currentSum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {
-2, 1, -3, 4, -1, 2, 1, -5, 4
};
long result = maxSubarraySum(nums);
System.out.println("Array: "
+ Arrays.toString(nums));
System.out.println("Maximum Subarray Sum: "
+ result);
}
}Output
Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Maximum Subarray Sum: 6
How Brute Force Works
- Select a starting index using the outer loop.
- Initialize a running sum to zero.
- Extend the subarray using the inner loop.
- Add each new element to the running sum.
- Compare the running sum with the maximum sum found so far.
- Continue until every possible contiguous subarray has been examined.
This implementation takes quadratic time because it uses two nested loops.
It is useful for learning, but Kadane's algorithm is more efficient for large arrays.
8. Time and Space Complexity
Let's compare Kadane's algorithm with the brute-force approach.
| Approach | Time Complexity | Auxiliary Space | Recommendation |
|---|---|---|---|
| Kadane's algorithm | O(n) | O(1) | Recommended |
| Kadane with indexes | O(n) | O(1) excluding extracted subarray | Returns actual subarray |
| Brute force | O(n²) | O(1) | Beginner alternative |
Here, n represents the number of elements in the array.
Why Is Kadane's Algorithm O(n)?
Kadane's algorithm processes every element exactly once.
At each position, it performs a constant number of comparisons and arithmetic operations.
Therefore, the time complexity is O(n).
Why Is the Auxiliary Space O(1)?
The basic implementation uses only two long variables and a loop index.
The number of variables does not increase with the array size.
Therefore, its auxiliary space complexity is O(1).
Why Is Brute Force O(n²)?
The brute-force implementation examines all possible contiguous subarrays using nested loops.
An array containing n elements has:
n × (n + 1) / 2
nonempty contiguous subarrays.
Because the implementation maintains an incremental sum, each inner-loop step takes constant time, resulting in O(n²) time complexity.
9. Handling Important Edge Cases
Case 1: All Negative Numbers
Input: [-8, -3, -6, -2, -5, -4] Output: Maximum Subarray Sum: -2
The maximum nonempty subarray contains only -2.
This is why the algorithm initializes currentSum and maxSum using the first array element rather than zero.
Case 2: All Positive Numbers
Input: [2, 3, 5, 1] Output: Maximum Subarray Sum: 11
The maximum subarray is the entire array.
Case 3: Single Element
Input: [-5] Output: Maximum Subarray Sum: -5
When the array contains only one element, that element is the maximum nonempty subarray.
Case 4: Array Contains Zeros
Input: [-2, 0, -1] Output: Maximum Subarray Sum: 0
The single-element subarray [0] produces the maximum sum.
Case 5: Mixed Positive and Negative Values
Input: [5, -2, 3, 4] Output: Maximum Subarray Sum: 10
The entire array has a sum of 10.
Notice that a maximum-sum subarray can include negative values when the surrounding positive values compensate for them.
Case 6: Empty Array
The implementations in this tutorial require a nonempty subarray.
Therefore, an empty input array is rejected with an IllegalArgumentException.
If your problem definition allows an empty subarray with sum zero, you will need to adjust the initialization and return behavior.
Case 7: Integer Overflow
The sum of several int values may exceed the range of a Java int.
The examples use long variables for running sums and the maximum sum.
This is sufficient to hold the sum of the elements of a Java int array within Java's array-length limits.
10. Common Mistakes to Avoid
Mistake 1: Initializing maxSum to Zero
If all array elements are negative, initializing maxSum to zero produces the wrong result for a nonempty-subarray problem.
Instead, initialize it using the first array element.
Mistake 2: Resetting the Running Sum Incorrectly
Kadane's algorithm compares the current number with the sum obtained by extending the previous subarray.
It does not simply discard every negative number.
A negative value may still belong to the maximum-sum subarray.
Mistake 3: Confusing Subarray and Subsequence
A subarray must contain consecutive elements.
You cannot skip an element in the middle and still call the result a contiguous subarray.
Mistake 4: Forgetting to Track Indexes
If an interviewer asks for the actual maximum-sum subarray, returning only the sum is not sufficient.
Track the starting and ending indexes as shown in Method 2.
Mistake 5: Using Nested Loops When Linear Time Is Required
Brute force takes O(n²) time.
Kadane's algorithm solves the problem in O(n) time and is generally the expected optimized solution.
11. Frequently Asked Questions
Q1. What is Kadane's algorithm in Java?
Kadane's algorithm is an efficient technique for finding the maximum sum of a contiguous subarray by tracking the best sum ending at each position.
Q2. What is the time complexity of Kadane's algorithm?
Its time complexity is O(n) because it traverses the array once.
Q3. What is the space complexity of Kadane's algorithm?
The basic implementation uses O(1) auxiliary space.
Q4. Does Kadane's algorithm work with negative numbers?
Yes. It handles positive and negative values, including arrays containing only negative numbers.
Q5. What is the maximum subarray sum of an all-negative array?
For the nonempty-subarray version, the result is the largest individual element.
Q6. Can Kadane's algorithm return the actual subarray?
Yes. Track the starting and ending indexes of the best subarray while updating the running and maximum sums.
Q7. What is the difference between a subarray and a subsequence?
A subarray contains consecutive elements. A subsequence can skip elements while preserving their relative order.
Q8. Is Kadane's algorithm a dynamic programming algorithm?
Yes. It uses the result of a smaller subproblem: the maximum sum of a subarray ending at the previous index.
Q9. Can Kadane's algorithm be used for minimum subarray sum?
Yes. A similar approach can find the minimum subarray sum by replacing maximum comparisons with minimum comparisons.
Q10. Is Kadane's algorithm better than brute force?
For this problem, Kadane's algorithm is significantly more efficient. It runs in linear time rather than quadratic time.
12. Conclusion
In this tutorial, you learned how to find the maximum subarray sum in Java using Kadane's algorithm.
- Kadane's algorithm: Finds the maximum sum of a contiguous subarray in
O(n)time. - Kadane with subarray tracking: Returns the maximum sum along with the actual subarray.
- Brute force: Examines all contiguous subarrays using nested loops.
For Java coding interviews, I recommend mastering Kadane's algorithm. It is an excellent example of how dynamic programming can turn a quadratic-time solution into a linear-time solution.
Once you understand the basic algorithm, practice related problems such as maximum circular subarray sum, minimum subarray sum, and maximum product subarray.
13. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java Math Class — Documentation for
Math.max(). - Java Arrays Class — Documentation for
Arrays.toString()andArrays.copyOfRange(). - Java Long Class — Documentation for the long data type and
Long.MIN_VALUE. - Java IllegalArgumentException Class — Documentation for reporting invalid method arguments.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment