Python Program to Find Maximum Subarray Sum

Use Kadane's algorithm in Python with max_ending_here = max(num, max_ending_here + num) and max_so_far = max(max_so_far, max_ending_here) to find the maximum subarray sum efficiently.

Examples

Input[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output6

Input[1, 2, 3, 4, 5]

Output15

Input[-1, -2, -3, -4]

Output-1

How to Think About It

To find the maximum sum of a contiguous subarray, move through the list while keeping track of the current sum of the subarray. If the current sum becomes negative, reset it to the current number because starting fresh might give a better sum. Keep track of the highest sum found so far during this process.

Algorithm

1

Initialize two variables: max_so_far and max_ending_here with the first element of the array.

2

Iterate through the array starting from the second element.

3

For each element, update max_ending_here to be the maximum of the current element and max_ending_here plus the current element.

4

Update max_so_far to be the maximum of max_so_far and max_ending_here.

5

After the loop ends, return max_so_far as the maximum subarray sum.

Code

python

def max_subarray_sum(nums):
    max_so_far = max_ending_here = nums[0]
    for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

Output

6

Dry Run

Let's trace the example [-2, 1, -3, 4, -1, 2, 1, -5, 4] through the code

1

Initialize

max_so_far = -2, max_ending_here = -2

2

Process 1

max_ending_here = max(1, -2 + 1) = 1; max_so_far = max(-2, 1) = 1

3

Process -3

max_ending_here = max(-3, 1 + -3) = -2; max_so_far = max(1, -2) = 1

4

Process 4

max_ending_here = max(4, -2 + 4) = 4; max_so_far = max(1, 4) = 4

5

Process -1

max_ending_here = max(-1, 4 + -1) = 3; max_so_far = max(4, 3) = 4

6

Process 2

max_ending_here = max(2, 3 + 2) = 5; max_so_far = max(4, 5) = 5

7

Process 1

max_ending_here = max(1, 5 + 1) = 6; max_so_far = max(5, 6) = 6

8

Process -5

max_ending_here = max(-5, 6 + -5) = 1; max_so_far = max(6, 1) = 6

9

Process 4

max_ending_here = max(4, 1 + 4) = 5; max_so_far = max(6, 5) = 6

max_ending_here	max_so_far
-2	-2
1	1
-2	1
4	4
3	4
5	5
6	6
1	6
5	6

Why This Works

Step 1: Track current subarray sum

The variable max_ending_here keeps the sum of the current subarray we are considering, resetting when it becomes less than the current number.

Step 2: Update maximum found

The variable max_so_far stores the highest sum found so far, updated whenever max_ending_here exceeds it.

Step 3: Efficient single pass

This approach only needs one pass through the list, making it efficient and simple without checking all subarrays.

Alternative Approaches

Brute Force

python

def max_subarray_sum_brute(nums):
    max_sum = nums[0]
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    return max_sum

print(max_subarray_sum_brute([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

Checks all subarrays, simple but slow (O(n^2)) for large lists.

Divide and Conquer

python

def max_crossing_sum(nums, left, mid, right):
    left_sum = float('-inf')
    total = 0
    for i in range(mid, left - 1, -1):
        total += nums[i]
        if total > left_sum:
            left_sum = total
    right_sum = float('-inf')
    total = 0
    for i in range(mid + 1, right + 1):
        total += nums[i]
        if total > right_sum:
            right_sum = total
    return left_sum + right_sum

def max_subarray_sum_divide(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    left_max = max_subarray_sum_divide(nums, left, mid)
    right_max = max_subarray_sum_divide(nums, mid + 1, right)
    cross_max = max_crossing_sum(nums, left, mid, right)
    return max(left_max, right_max, cross_max)

print(max_subarray_sum_divide([-2, 1, -3, 4, -1, 2, 1, -5, 4], 0, 8))

Uses recursion and combines results, faster than brute force but more complex.

Complexity: O(n) time, O(1) space

Time Complexity

Kadane's algorithm scans the list once, updating sums in constant time per element, so it runs in linear time O(n).

Space Complexity

It uses only a few variables to track sums, so it requires constant extra space O(1).

Which Approach is Fastest?

Kadane's algorithm is fastest and simplest for this problem compared to brute force (O(n^2)) and divide and conquer (O(n log n)).

Approach	Time	Space	Best For
Kadane's Algorithm	O(n)	O(1)	Large arrays, efficient
Brute Force	O(n^2)	O(1)	Small arrays, simple code
Divide and Conquer	O(n log n)	O(log n)	When recursion is preferred