Kadanes Algorithm
Java coding interview problem for Array Logic: Kadanes Algorithm.
Kadane's Algorithm is one of the most important array algorithms in programming interviews.
It solves the famous:
Maximum Subarray Sum Problem
The algorithm finds the contiguous subarray with the largest possible sum.
This problem is a foundation for:
- Dynamic Programming
- Sliding Window techniques
- Stock market problems
- Range optimization problems
- Data analytics
What is Kadane's Algorithm?
Kadane's Algorithm finds the maximum sum of a contiguous subarray in an integer array.
In simple words:
Find a continuous section of an array whose elements add up to the maximum value.
Example 1
Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]
Maximum subarray:
[4,-1,2,1]
Sum:
4 + (-1) + 2 + 1 = 6
Output:
6
Example 2
Input:
nums = [5,4,-1,7,8]
Maximum subarray:
[5,4,-1,7,8]
Sum:
23
Output:
23
Example 3
Input:
nums = [-2,-3,-1]
Maximum subarray:
[-1]
Output:
-1
Understanding Maximum Subarray Problem
A subarray is a continuous part of an array.
Example:
Array:
[1,2,3]
Possible subarrays:
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]
A subsequence is different.
Example:
[1,3]
is a subsequence.
But:
[1,3]
is not a subarray because element 2 is skipped.
Why is This Question Asked in Interviews?
Kadane's Algorithm is frequently asked because it tests:
- Array optimization
- Dynamic programming thinking
- Handling negative numbers
- Space optimization
- Decision-making at each element
Companies commonly ask variations:
- Maximum product subarray
- Maximum circular subarray
- Maximum sum rectangle
- Stock buy and sell
- Longest positive segment
Real-World Applications
Financial Market Analysis
Finding the best period of profit growth.
Example:
Daily changes:
[-3,5,-2,6,-1]
Best continuous growth period:
[5,-2,6]
Server Monitoring
Finding the period with maximum traffic increase.
Traffic changes:
[10,-5,20,-2]
Maximum increase:
[10,-5,20]
Data Analytics
Finding maximum scoring periods in:
- Sports performance
- Sales growth
- User engagement
Signal Processing
Finding strongest continuous signal segment.
Problem Statement
Given an integer array:
nums
find the contiguous subarray with the largest sum.
Return the maximum sum.
Constraints
Example:
1 <= nums.length <= 100000
Array values:
-10000 <= nums[i] <= 10000
Understanding Subarray Logic
Example:
nums:
[-2,1,-3,4,-1,2,1,-5,4]
Possible important segments:
[-2,1,-3]
[4,-1,2,1]
[-5,4]
Calculate:
4 + (-1) + 2 + 1
Result:
6
Maximum sum:
6
Brute Force Concept
The simplest idea:
Generate every possible subarray.
Calculate each sum.
Keep the maximum.
Example:
Array:
[1,-2,3]
Subarrays:
[1]
[-2]
[3]
[1,-2]
[-2,3]
[1,-2,3]
Calculate all sums.
Choose maximum.
Why Brute Force Is Slow?
Number of subarrays:
n(n+1)/2
For:
n = 100000
The number becomes extremely large.
Therefore:
O(n²)
or
O(n³)
approaches are not practical.
Mathematical Intuition Behind Kadane's Algorithm
At every element, we decide:
Should we:
- Continue the existing subarray?
OR
- Start a new subarray from this element?
Formula:
currentSum =
max(
current element,
currentSum + current element
)
Meaning:
If previous sum hurts us:
Discard it
Start fresh.
Example
Current sum:
-5
Current element:
4
Options:
Continue:
-5 + 4 = -1
Restart:
4
Choose:
4
Kadane's Algorithm Variables
We maintain two variables:
Current Sum
Represents:
Maximum sum ending at current position.
Maximum Sum
Represents:
Best answer found so far.
Array Visualization
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Process:
-2
1
-3
4
-1
2
1
-5
4
Track:
currentSum
maximumSum
Dry Run
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Initialize:
currentSum = -2
maximumSum = -2
Element: 1
Formula:
max(1, -2+1)
Values:
max(1,-1)
Current:
1
Maximum:
1
Element: -3
Formula:
max(-3,1-3)
Values:
max(-3,-2)
Current:
-2
Maximum:
1
Element: 4
Formula:
max(4,-2+4)
Values:
max(4,2)
Current:
4
Maximum:
4
Element: -1
Formula:
max(-1,4-1)
Current:
3
Maximum:
4
Element: 2
Current:
5
Maximum:
5
Element: 1
Current:
6
Maximum:
6
Element: -5
Current:
1
Maximum:
6
Element: 4
Current:
5
Maximum:
6
Final Answer:
6
Approach 1 — Brute Force Using Nested Loops
The easiest approach is checking every possible subarray.
Algorithm
- Select starting index.
- Select ending index.
- Calculate sum.
- Update maximum.
Java Program
public class MaximumSubarrayBruteForce {
public static int maxSubArray(
int[] nums) {
int maxSum =
Integer.MIN_VALUE;
for (int i = 0;
i < nums.length;
i++) {
for (int j = i;
j < nums.length;
j++) {
int sum = 0;
for (int k = i;
k <= j;
k++) {
sum += nums[k];
}
maxSum =
Math.max(
maxSum,
sum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums =
{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(
maxSubArray(nums));
}
}
Output
6
Step-by-Step Explanation
Input:
[-2,1,-3,4]
Check:
[-2]
[-2,1]
[-2,1,-3]
[1]
[1,-3]
[4]
Calculate each sum.
Largest:
4
Return maximum.
Complexity Analysis
There are three loops:
Time:
O(n³)
Space:
O(1)
Advantages
- Very easy to understand.
- Useful for learning.
- Works for all cases.
Drawbacks
- Extremely slow.
- Not suitable for large inputs.
Approach 2 — Prefix Sum Approach
Prefix sum improves brute force by avoiding repeated addition.
Prefix Sum Concept
Create an array:
prefix[i]
where:
prefix[i] = sum of elements from 0 to i
Example:
Array:
[1,2,3,4]
Prefix:
[1,3,6,10]
Subarray sum:
i to j
can be calculated:
prefix[j] - prefix[i-1]
Java Program
public class MaximumSubarrayPrefix {
public static int maxSubArray(
int[] nums) {
int n = nums.length;
int[] prefix =
new int[n];
prefix[0] = nums[0];
for (int i = 1;
i < n;
i++) {
prefix[i] =
prefix[i-1] +
nums[i];
}
int maxSum =
Integer.MIN_VALUE;
for (int i = 0;
i < n;
i++) {
for (int j = i;
j < n;
j++) {
int sum =
prefix[j] -
(i > 0 ?
prefix[i-1] : 0);
maxSum =
Math.max(
maxSum,
sum);
}
}
return maxSum;
}
}
Complexity Analysis
Prefix creation:
O(n)
Subarray checking:
O(n²)
Overall:
O(n²)
Space:
O(n)
Advantages
- Better than brute force.
- Demonstrates prefix sum technique.
- Useful for range queries.
Drawbacks
- Extra memory.
- Still slower than Kadane's Algorithm.
Approach 3 — Kadane's Algorithm (Optimal)
Kadane's Algorithm reduces the problem to a single traversal.
Time:
O(n)
Space:
O(1)
Algorithm
- Initialize:
currentSum = nums[0]
maxSum = nums[0]
- Traverse array.
- Update current sum:
currentSum =
max(nums[i],
currentSum + nums[i])
- Update maximum:
maxSum =
max(maxSum,currentSum)
- Return maxSum.
Java Program
public class KadanesAlgorithm {
public static int maxSubArray(
int[] nums) {
int currentSum =
nums[0];
int maxSum =
nums[0];
for (int i = 1;
i < nums.length;
i++) {
currentSum =
Math.max(
nums[i],
currentSum + nums[i]);
maxSum =
Math.max(
maxSum,
currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums =
{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(
maxSubArray(nums));
}
}
Output
6
Handling All Negative Numbers
A common interview edge case in Kadane's Algorithm is:
What happens when all numbers are negative?
Example:
nums = [-5,-2,-8,-1]
A common mistake is initializing:
currentSum = 0
and returning:
0
But the correct answer is:
-1
because the maximum subarray must contain at least one element.
Correct Initialization
Always initialize:
currentSum = nums[0]
maxSum = nums[0]
This handles:
- Positive numbers
- Negative numbers
- Mixed values
- Single element arrays
Example
Input:
[-5,-2,-8,-1]
Initialize:
currentSum = -5
maxSum = -5
Process:
-2
Calculate:
max(-2,-5-2)
Result:
-2
Maximum:
-2
Process:
-8
Current:
-8
Process:
-1
Current:
-1
Maximum:
-1
Answer:
-1
Finding Maximum Subarray Elements
Sometimes the interviewer asks:
Return the actual subarray, not only the sum.
Example:
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Output:
[4,-1,2,1]
Sum:
6
Modified Kadane's Algorithm
Maintain:
- Current start index
- Best start index
- Best end index
Algorithm
Variables:
currentStart
maxStart
maxEnd
Whenever we start a new subarray:
currentStart = i
Whenever maximum changes:
Store:
maxStart
maxEnd
Java Program
import java.util.Arrays;
public class MaximumSubarrayElements {
public static int[] maxSubArray(
int[] nums) {
int currentSum =
nums[0];
int maxSum =
nums[0];
int currentStart = 0;
int maxStart = 0;
int maxEnd = 0;
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] >
currentSum + nums[i]) {
currentSum = nums[i];
currentStart = i;
} else {
currentSum += nums[i];
}
if (currentSum > maxSum) {
maxSum = currentSum;
maxStart = currentStart;
maxEnd = i;
}
}
return Arrays.copyOfRange(
nums,
maxStart,
maxEnd + 1);
}
public static void main(String[] args) {
int[] nums =
{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(
Arrays.toString(
maxSubArray(nums)));
}
}
Output
[4,-1,2,1]
Step-by-Step Explanation
Input:
[-2,1,-3,4,-1,2,1,-5,4]
Maximum changes:
After:
4
Start:
index 3
Continue:
4,-1,2,1
Sum:
6
Store:
start = 3
end = 6
Circular Maximum Subarray Sum
A variation of Kadane's Algorithm:
Find maximum sum subarray where array can wrap around.
Example
Input:
[5,-3,5]
Normal Kadane:
[5]
Sum:
5
Circular case:
Wrap:
[5] + [5]
Result:
[5,-3,5]
Sum:
10-3
=
7
Formula
Circular Maximum:
max(
normal maximum,
total sum - minimum subarray sum
)
Why?
The circular maximum is equivalent to:
Remove the minimum middle portion.
Example:
[5,-3,5]
Total:
7
Minimum subarray:
[-3]
Remove:
7 - (-3)
Result:
10
Java Program
public class CircularKadane {
public static int maxCircularSum(
int[] nums) {
int totalSum = 0;
int maxSum =
nums[0];
int minSum =
nums[0];
int currentMax =
0;
int currentMin =
0;
for (int number : nums) {
currentMax =
Math.max(
number,
currentMax + number);
maxSum =
Math.max(
maxSum,
currentMax);
currentMin =
Math.min(
number,
currentMin + number);
minSum =
Math.min(
minSum,
currentMin);
totalSum += number;
}
if (maxSum < 0) {
return maxSum;
}
return Math.max(
maxSum,
totalSum - minSum);
}
}
Complexity Analysis
Time:
O(n)
Space:
O(1)
Prefix and Suffix Approach
Another way:
Calculate:
- Maximum prefix sum
- Maximum suffix sum
Useful for:
- Circular arrays
- Range problems
Java Streams Approach
Streams can implement maximum subarray using reduction.
However, Kadane's Algorithm is state-based, so Streams are not naturally suitable.
Example:
Arrays.stream(nums)
cannot directly maintain:
currentSum
maxSum
without custom collectors.
Kadane's Algorithm Mathematical Proof
At every index i:
Maximum subarray ending at i can only be:
Option 1:
Start new:
nums[i]
Option 2:
Extend previous:
previousSum + nums[i]
Therefore:
currentSum =
max(
nums[i],
previousSum + nums[i]
)
The global maximum is:
max(maxSum,currentSum)
Comparison of All Approaches
| Approach | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|
| Brute Force | O(n³) | O(1) | Learning |
| Prefix Sum | O(n²) | O(n) | Range calculations |
| Kadane | O(n) | O(1) | Maximum subarray |
| Modified Kadane | O(n) | O(1) | Return elements |
| Circular Kadane | O(n) | O(1) | Circular arrays |
Primitive vs Object Arrays
Primitive Array
Example:
int[]
Advantages:
- Faster execution
- Less memory
- No boxing
Recommended for:
- Large arrays
- Competitive programming
Object Array
Example:
Integer[]
Advantages:
- Works with Collections
- Supports generics
Common Interview Mistakes
Mistake 1
Initializing:
maxSum = 0
Problem:
Fails for:
[-5,-2,-1]
Mistake 2
Confusing subarray with subsequence.
Subarray:
Continuous
Subsequence:
Can skip elements
Mistake 3
Resetting current sum incorrectly.
Wrong:
if(sum < 0)
sum = 0;
This fails for all negative arrays.
Mistake 4
Ignoring integer overflow.
For large arrays use:
long
Edge Cases
| Input | Output |
|---|---|
[5] |
5 |
[-1] |
-1 |
[-2,-3,-1] |
-1 |
[1,2,3] |
6 |
[0,0,0] |
0 |
Interview Follow-up Questions
Q1. Return the actual subarray.
Q2. Find maximum circular subarray.
Q3. Find maximum product subarray.
Q4. Find maximum sum rectangle in matrix.
Q5. Explain Kadane mathematically.
Q6. Can Kadane handle negative numbers?
Q7. Difference between subarray and subsequence?
Q8. Modify Kadane for stock prices.
Related Problems
- Maximum Product Subarray
- Maximum Circular Subarray
- Best Time to Buy and Sell Stock
- Maximum Sum Rectangle
- Sliding Window Maximum
- Prefix Sum Problems
Key Takeaways
Kadane's Algorithm converts:
O(n²)
or
O(n³)
solutions into:
O(n)
by making a decision at every element.
Remember the formula:
currentSum =
max(
current element,
currentSum + current element
)
For interviews:
Preferred solution:
Kadane's Algorithm
Time: O(n)
Space: O(1)
Frequently Asked Interview Questions
Q1. Why does Kadane work?
Because the best subarray ending at each position depends only on the previous best ending position.
Q2. What if all numbers are negative?
Initialize with:
nums[0]
not zero.
Q3. Can Kadane return the subarray?
Yes.
Maintain start and end indexes.
Q4. Where is Kadane used?
Applications:
- Financial analysis
- Signal processing
- Performance analytics
- Optimization problems
Interview Tip
When asked:
"Find maximum subarray sum."
Explain the progression:
- Brute Force → O(n³)
- Prefix Sum → O(n²)
- Kadane → O(n)
The final optimal answer:
Kadane's Algorithm
Time Complexity: O(n)
Space Complexity: O(1)
Understanding the decision:
"Should I continue the current subarray or start fresh?"
is the key idea behind Kadane's Algorithm.