Mastery Points
0
Kadane's Algorithm in dsa
Context & Logic
Kadane's Algorithm is used to find the maximum sum of a contiguous subarray in an array of numbers. It is an efficient O(n) approach.
Example
function maxSubArray(nums) {
let maxSoFar = nums[0];
let currentMax = nums[0];
for (let i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
maxSoFar = Math.max(maxSoFar, currentMax);
}
return maxSoFar;
}Step-by-Step Logic
1
Initialize max_so_far and current_max with the first element.
2
Traverse from the second element to the end.
3
Update current_max: either start new subarray at current element or add current element to existing subarray.
4
Update max_so_far if current_max is better.
Complexity Metrics
Time Efficiency
O(n)
Memory Footprint
O(1)