Kadane's algorithm is a greedy approach to find the maximum sum of a contiguous subarray. It solves the problem in a single pass ($O(n)$ time), which is significantly better than the brute force $O(n^2)$ approach.

Imagine you're walking through a gold mine:

1. Some rooms have gold (positive numbers) and some have debt collectors (negative numbers).
2. You want to carry as much gold as possible.
3. If the total debt you've accumulated so far becomes greater than the gold you have (sum < 0), it's better to start fresh from the next room.
4. You keep a record of the highest total you ever reached during your journey.

---

The Core Decision

At every element in the array, you must ask yourself: "Should I add the current item to my existing streak, or should I start a new streak with just this item?"

You choose to start a new streak if the current item is actually higher than the current item + the entire previous streak.

Formula

$CurrentSum = max(item, CurrentSum + item)$ $MaxSum = max(MaxSum, CurrentSum)$

Complexity

• Time Complexity: $O(n)$ - We only loop through the array once.
• Space Complexity: $O(1)$ - We only use two variables to track sums.

---

javascript Standard
/**
 * Kadane's Algorithm implementation
 * Finds the maximum sum of a contiguous subarray
 */
function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];

  // Start from the second element
  for (let i = 1; i < nums.length; i++) {
    // Decision: Keep the streak or start fresh?
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    
    // Update the record if the current streak is the best
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

// Example
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 6 (Subarray: [4, -1, 2, 1])

---

Edge Cases

1. All Negative Numbers: The algorithm handles this! It will simply return the largest (least negative) single number.
2. Single Element Array: Handled by the initialization.

Follow-up Questions

• Find the actual subarray: Can you return the start and end indices of the subarray that gave the maximum sum? (Hint: Track the start index whenever you reset currentSum).
• Maximum Circular Subarray Sum: A popular variation involving two passes of Kadane and a total array sum calculation.
• Maximum Product Subarray: A similar greedy approach, but you must also keep track of the minProduct because two negatives multiplied become positive.