Kadane’s Algorithm 2 – Maximum Subarray Sum

Kadane’s Algorithm 2 – Maximum Subarray Sum
Problem Statement
You are given an integer array arr[]. The task is to find the maximum sum of a contiguous subarray (subarray must contain at least one element).
A subarray is a continuous portion of an array.

---

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

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

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

---

Objective
We need to find a continuous part of the array whose sum is maximum.
Instead of checking all subarrays (which would take O(n²)), we use Kadane’s Algorithm which solves this in O(n) time.

---

Kadane’s Algorithm Idea
The idea is simple:
• Keep track of the current subarray sum
• Keep track of the maximum sum found so far
• If the current sum becomes negative, reset it
Because a negative sum will reduce future sums.

---

Algorithm Steps

1. Initialize: o current_sum = arr[0] o max_sum = arr[0]
2. Traverse the array from second element
3. For each element: o current_sum = max(arr[i], current_sum + arr[i]) o max_sum = max(max_sum, current_sum)
4. Return max_sum ________________________________________ Python Implementation arr = [2, 3, -8, 7, -1, 2, 3]

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)

print("Maximum Subarray Sum:", max_sum)

---

Step-by-Step Example
For array:
[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
Final Answer = 11

---

Complexity Analysis
Type Complexity
Time Complexity O(n)
Space Complexity O(1)
This is very efficient because we traverse the array only once.

---

Edge Cases

1. All elements negative → return largest negative number
2. Single element array
3. Large arrays Example: [-2, -4] → Output: -2 ________________________________________ Conclusion Kadane’s Algorithm is an efficient way to find the maximum subarray sum. Instead of checking all subarrays, it uses a dynamic approach and runs in linear time O(n). This algorithm is very important for coding interviews and competitive programming.