Q11: How do you find the contiguous subarray with the largest sum using Kadane's Algorithm?
Maintain two variables: maxEndingHere and maxSoFar. Iterate through the array. For each element, decide whether to add it to the existing subarray sum or start a new subarray at the current element: maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]). Update maxSoFar = Math.max(maxSoFar, maxEndingHere).
Kadane's Maximum Subarray Solution
public class MaximumSubarray {
public static int maxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}💡 Tracks maximum subarray sums ending at each index in a single pass.
Key Takeaways
- Kadane's Algorithm executes Dynamic Programming in $O(n)$ time.
- Decides whether to extend the current sum or reset at the current element.
Knowledge Check
What does Kadane's Algorithm return if all elements in the input array are negative numbers (e.g., [-3, -1, -5])?