ASSIGNMENT 10

Maximum Subarray Sum (Kadane’s Algorithm Explained)

Finding the maximum sum of a contiguous subarray is one of the most famous problems in coding interviews.

Let’s break it down step by step 👇

📌 Problem Statement

Given an integer 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:
Subarray [7, -1, 2, 3] gives the maximum sum = 11

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

💡 Explanation:
Subarray [-2] gives the maximum sum = -2

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

💡 Explanation:
Entire array is the best subarray → 5 + 4 + 1 + 7 + 8 = 25

💡 Optimal Approach: Kadane’s Algorithm

This problem is best solved using Kadane’s Algorithm, which works in:

⏱ Time Complexity: O(n)
📦 Space Complexity: O(1)
🧠 Core Idea

At every index, decide:

👉 Should I continue the current subarray or start fresh?

We maintain two variables:

current_sum → sum of current subarray
max_sum → maximum sum found so far
🔄 Algorithm Steps

Initialize:

current_sum = arr[0]
max_sum = arr[0]

Traverse from index 1:

current_sum = max(arr[i], current_sum + arr[i])
max_sum = max(max_sum, current_sum)
Return max_sum
💻 Python Implementation
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 usage

arr = [2, 3, -8, 7, -1, 2, 3]
print(max_subarray_sum(arr))
🧾 Output
11
🔍 Dry Run (Quick Understanding)

For:

[2, 3, -8, 7, -1, 2, 3]
Index Element Current Sum Max Sum
0 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

If all elements are negative:

Return the largest (least negative) number

Example:

[-5, -2, -8] → Output: -2