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:
currentSum = max(current element, currentSum + current element)
And then we update:
maxSum = max(maxSum, currentSum)
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!
Comments
Loading comments...