🚀 Kadane’s Algorithm – Maximum Subarray Sum (Python)

Hi All,

Today I solved a very important problem in DSA: Kadane’s Algorithm to find the maximum subarray sum.

---

📌 Problem Statement

Given an array arr[], find the maximum sum of a contiguous subarray.

👉 A subarray is a continuous part of an array.

---

🔍 Examples

Example 1:

arr = [2, 3, -8, 7, -1, 2, 3]

Output:

11

👉 Subarray: [7, -1, 2, 3]

---

Example 2:

arr = [-2, -4]

Output:

-2

---

Example 3:

arr = [5, 4, 1, 7, 8]

Output:

25

---

💡 Approach

🔹 Brute Force (Not efficient)

• Check all subarrays
• Time Complexity: O(n²) ❌

---

🔹 Kadane’s Algorithm (Optimal)

👉 Idea:

• Keep track of current sum
• If current sum becomes negative → reset to 0
• Track maximum sum

---

🧠 Logic

At each step:

• Add current element to current_sum
• Update max_sum
• If current_sum < 0 → reset to 0

---

💻 Python Code

def max_subarray_sum(arr):
    max_sum = arr[0]
    current_sum = 0

    for num in arr:
        current_sum += num

        if current_sum > max_sum:
            max_sum = current_sum

        if current_sum < 0:
            current_sum = 0

    return max_sum

---

🔍 Dry Run

For:

arr = [2, 3, -8, 7, -1, 2, 3]

Steps:

• current = 2 → max = 2
• current = 5 → max = 5
• current = -3 → reset to 0
• current = 7 → max = 7
• current = 6 → max = 7
• current = 8 → max = 8
• current = 11 → max = 11

Final Output:

11

---

🖥️ Sample Output

Input: [2, 3, -8, 7, -1, 2, 3]
Output: 11

Input: [-2, -4]
Output: -2

Input: [5, 4, 1, 7, 8]
Output: 25

---

⚡ Complexity Analysis

• Time Complexity: O(n) ✅
• Space Complexity: O(1) ✅

---

🧠 Why Kadane’s Algorithm?

• Avoids checking all subarrays
• Works in single pass
• Very common interview question

---

✅ Conclusion

This problem helped me understand:

• Dynamic programming basics
• Handling negative values efficiently
• Optimizing brute force solutions

🚀 Kadane’s Algorithm is a must-know for placements!

---