Maximum Subarray Sum

Problem

Given an integer array arr[], find the maximum sum of a contiguous subarray.

The subarray must contain at least one element.
Example 1
Input: arr = [2, 3, -8, 7, -1, 2, 3]
Output: 11

Explanation: Subarray [7, -1, 2, 3] has the largest sum = 11.

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

Explanation: Subarray [-2] has the largest sum = -2.

Approach – Kadane’s Algorithm

Initialize:
max_current = arr[0] → max sum ending at current position
max_global = arr[0] → max sum found so far
Traverse the array from index 1:
max_current = max(arr[i], max_current + arr[i]) → either start new subarray or extend existing
max_global = max(max_global, max_current) → update maximum found

Python Code

class Solution:
def maxSubarraySum(self, arr):
max_sum = arr[0]
curr_sum = 0

    for num in arr:
        curr_sum += num

        if curr_sum > max_sum:
            max_sum = curr_sum

        if curr_sum < 0:
            curr_sum = 0

    return max_sum

Output
Maximum Subarray Sum: 11
Maximum Subarray Sum: -2
Maximum Subarray Sum: 25