Kadane’s Algorithm – Maximum Subarray Sum

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

A subarray is defined as a continuous portion 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

These constraints imply that a brute-force O(n²) solution will not work for large arrays. We need an O(n) solution, which is exactly what Kadane’s Algorithm provides.

Approach – Kadane’s Algorithm

Kadane’s Algorithm works by keeping track of two variables:

current_max – the maximum sum of the subarray ending at the current position.
max_so_far – the maximum sum found so far in the array.

Steps:

Initialize current_max = arr[0] and max_so_far = arr[0].
Traverse the array starting from index 1:
Update current_max = max(arr[i], current_max + arr[i]) → either extend the current subarray or start a new one
Update max_so_far = max(max_so_far, current_max) → update the overall maximum sum
After traversing the array, max_so_far contains the maximum sum of any contiguous subarray.

Python Implementation Code

class Solution:
def maxSubarraySum(self, arr):
# Initialize the first element as the starting max
max_so_far = arr[0]
current_max = arr[0]

    # Traverse the array starting from index 1

    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 usage

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 every element, the algorithm decides whether to continue the current subarray or start a new one.
max_so_far always keeps track of the maximum sum encountered so far.
The solution runs in O(n) time and uses O(1) space, making it efficient for large inputs.

Complexity Analysis
Time Complexity: O(n) – only a single pass through the array
Space Complexity: O(1) – only two variables are used

Kadane’s Algorithm is a must-know technique for array problems in interviews, competitive programming, and real-world applications where continuous maximum sum calculation is needed.