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

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

Hi All,

Today I worked on an important DSA problem: Kadane’s Algorithm, used to find the maximum sum of a subarray.

---

📌 Problem Statement

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

👉 A subarray is a continuous part of the 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

👉 Subarray: [-2]

---

Example 3:

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

Output:

25

👉 Subarray: [5, 4, 1, 7, 8]

---

💡 Approach

🔹 Key Idea

Instead of checking all subarrays (which is slow), we:

• Keep track of a current running sum
• If the sum becomes negative → reset it
• Track the maximum sum found so far

---

🧠 Step-by-Step Logic

1. Initialize:

   • current_sum = 0
   • max_sum = arr[0]

2. Traverse the array:

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

---

💻 Python Code

def max_subarray_sum(arr):
    current_sum = 0
    max_sum = arr[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:

• 2 → current = 2, max = 2
• 3 → current = 5, max = 5
• -8 → current = -3 → reset to 0
• 7 → current = 7, max = 7
• -1 → current = 6
• 2 → current = 8
• 3 → current = 11, max = 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 a single pass
• Efficient and widely used in interviews

---

✅ Conclusion

This problem helped me understand:

• How to optimize brute-force solutions
• Handling negative numbers efficiently
• Writing clean and efficient code

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

---