Maximum Subarray Sum (Kadane’s Algorithm)

📌 Definition:

📖 Detailed Explanation:

Kadane’s algorithm keeps a running current-sum: at each element, either extend the previous subarray or start fresh at the current element (current = max(x, current + x)), tracking the best seen. O(n) time, O(1) space. Handle all-negative arrays by seeding with the first element.

💻 Solutions:

• Java
• JavaScript
• Python

public static int maxSubArray(int[] a) {
    int best = a[0], current = a[0];
    for (int i = 1; i < a.length; i++) {
        current = Math.max(a[i], current + a[i]);
        best = Math.max(best, current);
    }
    return best;
}

function maxSubArray(a) {
  let best = a[0], current = a[0];
  for (let i = 1; i < a.length; i++) {
    current = Math.max(a[i], current + a[i]);
    best = Math.max(best, current);
  }
  return best;
}

def max_subarray(a):
    best = current = a[0]
    for x in a[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

🔑 Key Points:

• current = max(x, current + x)
• best = max(best, current)
• Seed with the first element for all-negative inputs
• O(n) time, O(1) space

🌍 Real-World Example: