Find Maximum Subarray Sum using Kadane's Algorithm - Optimal Solution

Given an array of integers (which may include negative numbers), your task is to find the maximum sum of any contiguous subarray.

This problem is also known as the Maximum Subarray Problem.

• You must return the maximum sum possible by choosing a continuous range of elements from the array.
• If the array is empty, return 0.

Use Kadane's Algorithm to solve it efficiently in linear time.

Step-by-Step Solution to Maximum Subarray Sum Problem

Understanding the Problem

We are given an array of integers. Our task is to find the maximum sum of a contiguous subarray. That means we must select a subarray (a sequence of elements that appear consecutively) such that the sum of its elements is as large as possible.

We’ll explore this problem step-by-step using examples, and then apply a proven technique called Kadane’s Algorithm to solve it efficiently.

Let's Begin with an Example

Consider the array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We need to find a contiguous subarray that gives the highest sum. Visually exploring this array, we notice that the subarray [4, -1, 2, 1] adds up to 6, which is the maximum possible sum of any contiguous subarray in this case.

Step-by-Step Approach

We start scanning the array from left to right, keeping track of two variables:

• currentSum: The sum of the current subarray being considered
• maxSum: The highest sum found so far

At each element, we decide:

• Should we include this element in the current subarray?
• Or start a new subarray starting from this element?

This decision is made by taking the maximum of:

And then we update:

Intuition for Beginners

If the previous sum is helping us grow (i.e., it's positive), we add the current number to it. But if the previous sum is dragging us down (i.e., it’s negative), we just start fresh from the current number. We always keep track of the maximum we've seen so far.

Understanding Edge Cases

1. All Positive Numbers

Input: [1, 2, 3, 4]
Every number is good for the sum, so we take the whole array. Result = 10

2. All Negative Numbers

Input: [-3, -2, -1]
All sums are negative, so the least negative (i.e., closest to zero) single number is the best. Result = -1

3. Mixed Positive and Negative

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Kadane’s Algorithm picks [4, -1, 2, 1] as the best subarray. Result = 6

4. Zeros or Zero as Maximum

Input: [0, 0, 0] or [-2, -1, 0, -3]
Sometimes zero is the best possible sum, especially when no positive numbers exist. Result = 0

5. Single Element Array

Input: [5] or [-4]
The only element is the result. Result = the element itself

6. Empty Array

Input: []
There are no elements to consider. By convention, the result is 0 or may be undefined depending on the context.

Why Kadane’s Algorithm Works So Well

Instead of trying all possible subarrays (which takes O(n²) time), Kadane’s Algorithm goes through the array just once – that’s O(n) time!

It continuously maintains the best sum seen so far and handles all types of arrays—positive, negative, mixed, zero, or even empty. That's why it's one of the most elegant algorithms in dynamic programming!

1. Given an integer array arr.
2. Initialize two variables: max_sum and current_sum with the value of the first element.
3. Iterate through the array starting from index 1.
4. At each step, update current_sum as the maximum of the current element or current_sum + current_element.
5. Update max_sum if current_sum is greater than max_sum.
6. After the loop, return max_sum as the result.

O(1)

Explanation: Kadane's Algorithm uses only constant space with a few variables (max_sum and current_sum) to track the state—no extra arrays or recursion are used.