⚡ Kadane’s Algorithm – Maximum Subarray Sum

Kadane’s Algorithm is a powerful and efficient way to find the maximum sum of a contiguous subarray.
It is one of the most frequently asked problems in coding interviews.

---

📌 Problem Statement

Given an array arr[], find the maximum sum of a subarray (with at least one element).

👉 A subarray is a continuous part of the array.

---

🔍 Examples

Example 1:

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

Example 2:

Input:  [-2, -4]
Output: -2
Explanation: Subarray = [-2]

Example 3:

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

---

🧠 Intuition

At every element, we make a decision:

👉 Do we extend the current subarray or start a new one?

• If the current sum becomes negative → discard it
• Start fresh from the current element

---

🔄 Approach (Kadane’s Algorithm)

Step-by-Step:

1. Initialize:

• current_sum = arr[0]

• max_sum = arr[0]

  1. Traverse from index 1:

• current_sum = max(arr[i], current_sum + arr[i])

• max_sum = max(max_sum, current_sum)

  1. Return max_sum

---

💻 Python Code

```python id="k4"
def max_subarray_sum(arr):
current_sum = arr[0]
max_sum = arr[0]

for i in range(1, len(arr)):
    current_sum = max(arr[i], current_sum + arr[i])
    max_sum = max(max_sum, current_sum)

return max_sum

Example

print(max_subarray_sum([2, 3, -8, 7, -1, 2, 3]))

---

## 🧾 Dry Run

For:



```id="k5"
arr = [2, 3, -8, 7, -1, 2, 3]

Element	Current Sum	Max Sum
2	2	2
3	5	5
-8	-3	5
7	7	7
-1	6	7
2	8	8
3	11	11

---

⚡ Complexity

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

---

🔥 Why This Works

• Avoids checking all subarrays (O(n²))
• Uses a greedy + dynamic approach
• Tracks best sum ending at each index

---

⚠️ Edge Case

If all elements are negative:

👉 Return the maximum element

✔ Kadane’s algorithm handles this automatically

---

🏁 Conclusion

Kadane’s Algorithm is:

✔ Fast (linear time)
✔ Simple
✔ Essential for interviews