Kadane’s Algorithm to Find 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 and maintain:

• Current sum of subarray
• Maximum sum found so far

If the current sum becomes less than the current element, we start a new subarray.

Code:

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

Explanation:

• current_sum tracks the best sum ending at current index
• If adding previous sum is bad, we restart from current element
• max_sum stores the final answer Time Complexity: O(n), single traversal

Space Complexity:
O(1), no extra space