Q6: Maximum Subarray (Kadane's Algorithm)
Find the contiguous subarray with the largest sum within an array of numbers using Kadane's dynamic programming algorithm.
Kadane's Algorithm Solution
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 (subarray [4,-1,2,1])💡 currentSum updates to either the current item alone or current item plus previous running sum, whichever is greater, while maxSum tracks global maximum.
Key Takeaways
- Kadane's algorithm runs in linear O(n) time complexity with O(1) space.
- At each element, decides whether to extend the current sum or start a new subarray sum.
Knowledge Check
What is the time complexity of Kadane's Algorithm?