CA 10 - Kadanes Algorithm

Problem

Given an integer array arr[], the task is to find the maximum sum of a subarray containing at least one element.

A subarray is a continuous part of an array.

Output

Example 1
Output: 11
Example 2
Output: -2
Example 3
Output: 25

My Approach

To solve this problem, I used Kadane’s Algorithm.

I keep track of two variables:

current_sum to store the sum of the current subarray
max_sum to store the maximum sum found so far

I iterate through the array:

At each element, I decide whether to start a new subarray or continue the existing one
I update current_sum as the maximum of the current element or the sum of current element and previous current_sum
Then I update max_sum if current_sum is greater

This works because it efficiently keeps track of the best possible subarray ending at each position.

This approach is efficient because:

It requires only one traversal
It uses constant extra space
Code

def max_subarray_sum(arr):
    current_sum = arr[0]
    max_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum