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:

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))