⚡ Kadane's Algorithm – Maximum Subarray Sum (Step-by-Step)

Kadane’s Algorithm is one of the most important problems in Data Structures and Algorithms.
It helps you find the maximum sum of a contiguous subarray in an efficient way.

---

📌 Problem Statement

Given an array arr[], find the maximum sum of a subarray (containing 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: [7, -1, 2, 3]

Example 2:

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

Example 3:

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

---

🧠 Intuition

At each step, we decide:

👉 Should we continue the current subarray or start a new one?

If adding the current element improves the sum → continue
If not → start fresh from current element

---

🔄 Approach: Kadane’s Algorithm (Optimal)

Step-by-Step:

1. Initialize:

• current_sum = arr[0]

• max_sum = arr[0]

  1. Traverse from index 1 to end:

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

• max_sum = max(max_sum, current_sum)

  1. Return max_sum

---

💻 Python Code

```python id="2p7v1n"
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 (Step-by-Step)

For:



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

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

---

⚡ Time and Space Complexity

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

---

🔥 Why Kadane’s Algorithm Works

• It avoids checking all subarrays (O(n²))
• Uses dynamic programming idea
• Keeps track of the best subarray ending at each index

---

🧩 Edge Case (Important)

👉 When all elements are negative:

• The answer is the maximum single element

Kadane’s algorithm handles this automatically ✔

---

🚀 Bonus: Print the Subarray (Advanced)

```python id="u9z6kp"
def max_subarray(arr):
max_sum = arr[0]
current_sum = arr[0]
start = end = temp = 0

for i in range(1, len(arr)):
    if arr[i] > current_sum + arr[i]:
        current_sum = arr[i]
        temp = i
    else:
        current_sum += arr[i]

    if current_sum > max_sum:
        max_sum = current_sum
        start = temp
        end = i

return max_sum, arr[start:end+1]

---

## 🏁 Conclusion

Kadane’s Algorithm is:

✔ Simple
✔ Efficient
✔ Widely used in interviews

Once you understand this, you can solve many advanced problems related to arrays and dynamic programming.