Maximum Subarray Sum Using Kadane’s Algorithm

Problem Statement

You are given an integer array arr[]. Your task is to find the maximum sum of a subarray containing at least one element.

A subarray is defined as a continuous part of an array.

Examples
Example 1:

Input: arr = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray [7, -1, 2, 3] has the largest sum 11.

Example 2:

Input: arr = [-2, -4]
Output: -2
Explanation: The subarray [-2] has the largest sum -2.

Example 3:

Input: arr = [5, 4, 1, 7, 8]
Output: 25
Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25.
Constraints
1 ≤ arr.size() ≤ 10^5
-10^4 ≤ arr[i] ≤ 10^4

Given these constraints, a brute-force approach with O(n²) time complexity would be inefficient. We need a linear-time solution.

Approach

Initialize two variables:
max_so_far -stores the maximum sum found so far
current_max - stores the maximum sum ending at the current position

Traverse the array from the second element:
current_max = max(arr[i], current_max + arr[i]) - decide whether to extend the current subarray or start a new one
max_so_far = max(max_so_far, current_max) - update the overall maximum sum
After the loop, max_so_far contains the maximum subarray sum.

Python Code
class Solution:
def maxSubarraySum(self, arr):
max_so_far = arr[0]
current_max = arr[0]

    for i in range(1, len(arr)):
        current_max = max(arr[i], current_max + arr[i])
        max_so_far = max(max_so_far, current_max)

    return max_so_far

Example input and output
arr1 = [2, 3, -8, 7, -1, 2, 3]
arr2 = [-2, -4]
arr3 = [5, 4, 1, 7, 8]

ob = Solution()
print(ob.maxSubarraySum(arr1)) # Output: 11
print(ob.maxSubarraySum(arr2)) # Output: -2
print(ob.maxSubarraySum(arr3)) # Output: 25

Explanation
At each element, we decide whether to continue the current subarray or start a new subarray.
max_so_far always keeps track of the maximum sum found so far.