Kadane Algorithm
Imagine you have a stock chart and you want to find the best day to buy and sell to maximize profit. You need to find the contiguous subarray with the largest sum. Kadane's Algorithm solves this elegantly in O(n).
The idea is simple: keep track of the maximum sum ending at the current position. For each element, either start a new subarray at that element, or extend the previous subarray.
Kadane's algorithm (maximum subarray sum):
public static int maxSubarraySum(int[] arr) {
int maxSoFar = arr[0];
int maxEndingHere = arr[0];
for (int i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
Example: For array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6 (from index 3 to 6: 4 + -1 + 2 + 1).
Kadane's algorithm works even if all numbers are negative (returns the maximum element). If you need to handle empty subarray case, you can return 0 instead.
Two Minute Drill
- Kadane's algorithm finds contiguous subarray with maximum sum in O(n).
- Maintain max ending at current position and overall max.
- At each step: decide to start new subarray or extend previous.
- Variant: return subarray indices, handle all negative.
- Widely used in coding interviews.
Need more clarification?
Drop us an email at career@quipoinfotech.com