Kadane’s Algorithm – Maximum Subarray Sum

Problem Statement:
Given an integer array, find the maximum sum of a contiguous subarray.

Example:
Input: [2, 3, -8, 7, -1, 2, 3]
Output: 11

Approach (Kadane’s Algorithm):

We iterate through the array while keeping track of:

• Current subarray sum
• Maximum sum found so far At each step, we decide whether to continue the current subarray or start a new one.

Code:

def max_subarray_sum(arr):
max_sum = arr[0]
current_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

Explanation:

• current_sum stores the maximum sum ending at current position
• If adding the current element reduces the sum, we start fresh
• max_sum keeps track of the overall maximum

Time Complexity:
O(n), single pass through array

Space Complexity:
O(1), constant space