Maximum Subarray Sum (Kadane’s Algorithm)

Difficulty: Medium, Asked-in: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Zoho.

Key takeaways

• One of the best problems to learn time and space complexity optimization using various approaches.
• The idea behind Kadane's algorithm is intuitive and worth exploring. We can use similar ideas to solve several coding problems efficiently.

Let’s understand the problem

Given an array X[] of n integers, write a program to find the maximum sum of a subarray among all subarrays. A subarray of array X[] is a contiguous segment of elements from X[i] to X[j], where 0 <= i <= j <= n - 1.

• If array contains all non-negative numbers, the max subarray sum will be the sum of the entire array.
• Several subarrays may have the same maximum sum, but we only need to return the value of the maximum subarray sum.

Example 1

Input: X[] = [-4, 5, 7, -6, 10, -15, 3], Output: 16

Explanation: The subarray [5, 7, -6, 10] has the maximum sum.

Example 2

Input: X[] = [-3, 2, -1, 4, -2], Output: 5

Explanation: The subarray [2, -1, 4] has the maximum sum.

Example 3

Input: X[] = [5, 7, 6, 10, 3], Output: 31

Explanation: All array elements are non-negative. So the maximum subarray sum would be the sum of the entire array.

Discussed solution approaches

• Brute force approach  using three nested loops
• Using two nested loops
• Using divide and conquer idea similar to the merge sort
• Using dynamic programming : Using single loop and O(n) space
• Kadane's algorithm: Using single loop and variables

Brute force approach  using three nested loops

Solution idea

The most basic solution is to explore all possible subarrays (for all i and j, where i ≤ j), calculate the sum of each subarray and return the maximum among them.

Solution steps

1. We declare a variable maxSubarraySum to store the maximum subarray sum found so far.
2. We explore all subarrays (i, j) using a nested loop: the outer loop runs from i = 0 to n - 1, and the inner loop runs from j = i to n - 1.
3. For each subarray (i, j), we run another loop from k = i to j and calculate the subarray sum between them. We store this value in a variable subarraySum.
4. If (subarraySum > maxSubarraySum), we update maxSubarraySum with subarraySum.

At the end of the nested loop, we return maxSubarraySum.

Solution code C++

int findMaxSubarraySum(int X[], int n)
{
    int maxSubarraySum = INT_MIN;
    for (int i = 0; i < n; i = i + 1)
    {
        for (int j = i; j < n; j = j + 1)
        { 
            int subarraySum = 0;
            for (int k = i; k <= j; k = k + 1)
                subarraySum = subarraySum + X[k];
            if (subarraySum > maxSubarraySum)
                maxSubarraySum = subarraySum;
        }
    }
    return maxSubarraySum;
}

Solution code Python

def findMaxSubarraySum(X, n):
    maxSubarraySum = -maxsize
    for i in range(n):
        for j in range(i, n):
            subarraySum = 0
            for k in range(i, j + 1):
                subarraySum = subarraySum + X[k]
            if subarraySum > maxSubarraySum:
                maxSubarraySum = subarraySum
    return maxSubarraySum

Time and space complexity analysis

We are using three nested loops: Exploring each subarray using two outer loops and calculating their sum using the innermost loop. So time complexity = O(n^3). Note: You can explore analysis of loop blog for understanding the exact analysis of this loop.

We are using constant extra space, so space complexity = O(1).

Using two nested loops

Now, the critical questions are: Can we optimize the above approach further? Is it necessary to run the innermost loop from k = i to j? Let's think!

Solution idea

If we observe closely, we can easily calculate the subarray sum from i to j + 1 in O(1), if we know the sub-array sum from i to j. Here is the formula: Subarray sum from i to j + 1 = Subarray sum from i to j + X[j + 1].

This is the optimized version of the above approach. Here we can use only two nested loops: the outer loop to pick the starting index, and the inner loop to calculate the running sum of all sub-arrays starting from that index. So we can easily avoid the innermost loop to calculate the sum of each subarray every time.

Solution code C++

int findMaxSubarraySum(int X[], int n)
{
    int maxSubarraySum = INT_MIN;
    for (int i = 0; i < n; i = i + 1)
    {  
        int subarraySum = 0;
        for (int j = i; j < n; j = j + 1)
        { 
            subarraySum = subarraySum + X[j];
            if (subarraySum > maxSubarraySum)
                maxSubarraySum = subarraySum;
        }
    }
    return maxSubarraySum;
}

Solution code Python

def findMaxSubarraySum(X, n):
    maxSubarraySum = -maxsize
    for i in range(n):
        subarraySum = 0
        for j in range(i, n):
            subarraySum =  subarraySum + X[j]
            if subarraySum > maxSubarraySum:
                maxSubarraySum = subarraySum
    return maxSubarraySum

Time and space complexity analysis

We are using two nested loops to explore each subarray and performing O(1) operation at each iteration. Total count of loop iterations = Total count of different subarrays = n + n - 1 + n - 2 + ... + 2 + 1 = n(n + 1)/2 = O(n²). So time complexity = Total count of loop iterations * O(1) = O(n²).

We are using constant extra space, so space complexity = O(1).

Using divide and conquer idea similar to merge sort

Now critical questions are: Can we improve time complexity further? Can we solve this problem using smaller sub-problems or the divide and conquer approach? Let's think!

Solution idea

Suppose we want to calculate the maximum sub-array sum of the array X[l...r], where l and r are the left and right ends. Now we divide the array into two equal subarrays by calculating the mid-index: X[l, mid] and X[mid + 1, r]. If we observe, the sub-array X[i, j] with the maximum sum must lie in one of the following places:

• Entirely in the left subarray X[l, mid], where l ≤ i ≤ j ≤ mid.
• Entirely in the right subarray X[mid + 1, r], where mid + 1 ≤ i ≤ j ≤ r.
• A subarray crossing the mid-point, where low ≤ i ≤ mid ≤ j ≤ r. This includes some of the rightmost elements of the left subarray and some of the leftmost elements of the right subarray.

We can recursively find the maximum sub-array sum of X[l, mid] and X[mid + 1, r] because these two are smaller instances of the problem of finding the maximum sub-array sum.

int leftMaxSum = findMaxSubarraySum (X, l, mid)
int rightMaxSum = findMaxSubarraySum (X, mid + 1, r)

Now we need to calculate the maximum sub-array that crosses the mid-point and take the maximum of all three possibilities to get overall max subarray sum.

int crossingMaxSum = maxCrossingSum(X, l, mid, r)
return max(leftMaxSum, rightMaxSum, crossingMaxSum)

Base case: When l == r, there is only one element in the array, and we can directly return the maximum subarray sum as X[l] or X[r]. This is the smallest version of the problem, where the recursion will return the value directly.

Solution pseudocode

int getMaxSubarraySum (int X[], int l, int r)
{
    if (l == r)
        return X[l]
    else
    {
        int mid = l + (r - l)/2
        int leftMaxSum = getMaxSubarraySum (X, l, mid)
        int rightMaxSum = getMaxSubarraySum (X, mid + 1, r)
        int crossingMaxSum = maxCrossingSum (X, l, mid, r)
        return max (leftMaxSum, rightMaxSum, crossingMaxSum)
   }
}

Combine part  implementation:  maxCrossingSum(X, l, mid, r)

The maximum subarray sum crossing the midpoint will include two subarrays: Subarray X[i, mid] with the maximum sum in the left part and subarray X[mid + 1, j] with the maximum sum in the right part. So, to get the overall maximum sum crossing the midpoint, we need to find these two sums by separately traversing the left and right parts and adding their values.

Here are the steps:

Step 1: We find the maximum contiguous sum of the left half, X[l, mid].

• We initialize a variable sum to store the continuous sum from mid to some index i and a variable maxLeftSum to store the maximum sum found so far in the left part.
• We run a loop starting from index i = mid to l, calculate the contiguous sum, and store it in the variable sum. Whenever sum > maxLeftSum, we update maxLeftSum with sum.

int sum = 0
int maxLeftSum = INT_MIN
for(int i = mid; i <= l; i = i - 1)
{
    sum = sum + X[i]
    if (sum > maxLeftSum)            
        maxLeftSum = sum
}

Step 2: Now we find the maximum contiguous sum of the right half, X[mid + 1, r].

• We use the same variable sum and initialize it with 0.
• We initialize a variable maxRightSum to store the maximum sum found so far in the right part. 
• Now we run a loop from j = mid + 1 to r, calculate the contiguous sum, and store it in the variable sum. Whenever sum > maxRightSum, we update maxRightSum with sum.

sum = 0
int maxRightSum = INT_MIN
for(int i = mid + 1; i <= r; i = i + 1)
{
    sum = sum + X[i]
    if (sum > maxRightSum)
        maxRightSum = sum
}

Step 3: Finally, to get the maximum contiguous subarray sum crossing the mid, we return the sum of variables maxLeftSum and maxRightSum.

Solution code C++

int maxCrossingSum(int X[], int l, int mid, int r)
{
    int sum = 0;
    int maxLeftSum = INT_MIN;
    for (int i = mid; i >= l; i = i - 1)
    {
        sum = sum + X[i];
        if (sum > maxLeftSum)
            maxLeftSum = sum;
    }
    sum = 0;
    int maxRightSum = INT_MIN;
    for (int i = mid + 1; i <= r; i = i + 1)
    {
        sum = sum + X[i];
        if (sum > maxRightSum)
            maxRightSum = sum;
    }
    return (maxLeftSum + maxRightSum);
}

int findMaxSubarraySum(int X[], int l, int r)
{
    if (l == r)
        return X[l];
    else
    {
        int mid = l + (r - l) / 2;
        int leftMaxSum = findMaxSubarraySum(X, l, mid);
        int rightMaxSum = findMaxSubarraySum(X, mid + 1, r);
        int crossingMaxSum = maxCrossingSum(X, l, mid, r);
        return max({leftMaxSum, rightMaxSum, crossingMaxSum});
    }
}

Solution code Python

def maxCrossingSum(X, l, mid, r):
    sum = 0
    maxLeftSum = -sys.maxsize
    for i in range(mid, l-1, -1):
        sum = sum + X[i]
        maxLeftSum = max(maxLeftSum, sum)

    sum = 0
    maxRightSum = -sys.maxsize
    for i in range(mid+1, r+1):
        sum = sum + X[i]
        maxRightSum = max(maxRightSum, sum)

    return maxLeftSum + maxRightSum

def findMaxSubarraySum(X, l, r):
    if l == r:
        return X[l]
    else:
        mid = l + (r-l)//2
        leftMaxSum = findMaxSubarraySum(X, l, mid)
        rightMaxSum = findMaxSubarraySum(X, mid+1, r)
        crossingMaxSum = maxCrossingSum(X, l, mid, r)
        return max(leftMaxSum, rightMaxSum, crossingMaxSum)

Time and space complexity analysis

Suppose T(n) is the time complexity of finding the maximum subarray sum using divide and conquer approach. To calculate the overall time complexity, we need to add the time complexities of the divide, conquer, and combine steps.

• For the base case (n = 1), the algorithm takes constant time => T(1) = O(1).
• We only need to calculate mid to divide the array. So the time complexity of divide part = O(1). 
• We are solving two subproblems of size n/2. So the time complexity of conquer part = 2T(n/2).
• To find the maximum subarray sum crossing the mid, we run two single loops in the opposite direction. In the worst case, each loop will run n/2 times. So the time complexity of combine part = O(n).

Final recurrence relation

• T(n) = O(1), if n = 1.
• T(n) = 2T(n/2) + O(n), if n > 1.

This recurrence is the same as a recurrence relation of the merge sort. So overall time complexity = O(nlogn). For a better understanding of this analysis, you can explore analysis of recursion blog.

Space complexity is equal to the size of the recursion call stack, which depends on the height of the recursion tree. At each stage, the input size decreases by 2, so the height of the recursion tree will be O(logn). Space complexity = O(logn). Think!

Using dynamic programming

Solution idea

If we observe, the maximum subarray must be ending at some index in the array. So one idea would be to find the maximum subarray sum ending at all indexes and store their values in an extra memory. Now we can easily get the max subarray sum of the whole array by finding the maximum value in the extra memory. The critical question is: How can we implement this? Let's think!

Suppose we take an array maxSumEnding[] of size n, where maxSumEnding[i] denotes the maximum subarray sum ending at index i. If we know the maxSumEnding[i - 1], we can easily calculate the maxSumEnding[i]. Here are the insights:

• maxSumEnding[i] always includes the value X[i].
• If (maxSumEnding[i - 1] > 0), we need to include maxSumEnding[i - 1] to calculate maxSumEnding[i]. The idea is simple: maxSumEnding[i - 1] + X[i] will be always greater than X[i]. So in this case, we update maxSumEnding[i] = maxSumEnding[i - 1] + X[i].
• If (maxSumEnding[i -1] < 0), we need to ignore maxSumEnding[i -1] to calculate maxSumEnding[i], because maxSumEnding[i - 1] + X[i] will be always less than X[i]. So we just update maxSumEnding[i] = X[i].
• In simpler terms, we can also write: maxSumEnding[i] = max(maxSumEnding[i - 1] + X[i], X[i]).

Finally, to get the maximum subarray sum of the whole array, we return the maximum value stored in the array maxSumEnding[]. This problem falls under the dynamic programming category because we store the solution of sub-problems and solve the larger problem using the solution of smaller sub-problems.

Solution steps

1. We create an extra array maxSumEnding[] of size n.
2. We initialize the array with the first value, i.e., maxSumEnding[0] = X[0].

3. Now we traverse the array from i = 1 to n - 1. At ith iteration, we calculate the max subarray sum ending at index i and store it at maxSumEnding[i].

   • If (maxSumEnding[i - 1] < 0), maxSumEnding[i] = X[i].
   • Otherwise, maxSumEnding[i] = X[i] + maxSumEnding[i - 1].
4. We return the maximum value stored in maxSumEnding[].

Solution code C++

int findMaxSubarraySum(int X[], int n)
{
    int maxSumEnding[n];
    maxSumEnding[0] = X[0];
    
    for (int i = 1; i < n; i = i + 1)
    {
        if (maxSumEnding[i - 1] > 0)
            maxSumEnding[i] = X[i] + maxSumEnding[i - 1];
        else
            maxSumEnding[i] = X[i];
    }
    
    int maxSubarraySum = INT_MIN;
    for (int i = 0; i < n; i = i + 1)
        maxSubarraySum = max(maxSubarraySum, maxSumEnding[i]);

    return maxSubarraySum;
}

Solution code Python

def findMaxSubarraySum(X, n):
    maxSumEnding = [0] * n
    maxSumEnding[0] = X[0]
    
    for i in range(1, n):
        if maxSumEnding[i - 1] > 0:
            maxSumEnding[i] = X[i] + maxSumEnding[i - 1]
        else:
            maxSumEnding[i] = X[i]
    
    maxSubarraySum = -sys.maxsize
    for i in range(n):
        maxSubarraySum = max(maxSubarraySum, maxSumEnding[i])

    return maxSubarraySum

Time and space complexity analysis

We are traversing array twice using single loop and performing O(1) operation at each iteration. Time complexity = O(n) + O(n) = O(n). Space complexity = O(n), for extra array maxSumEnd[n].

Efficient solution using Kadane's algorithm

Solution idea

Now, let's address the critical questions: Can we solve this problem in O(1) space? Can we solve this problem in a single traversal? Here's an optimized solution idea using Kadane's algorithm.

• Based on the previous approach, we can calculate the maximum subarray sum ending at the ith index using the maximum subarray sum ending at the (i - 1)th index. So, we can easily track this value for each index using a variable (maxSumEndingHere) in a single loop i.e. maxSumEndingHere = max(maxSumEndingHere + X[i], X[i]).
• The value of the maximum subarray sum will be the maximum of all subarray sums ending at index i. So, we can also track this value in a variable (maxSumSoFar) within the same loop i.e. if (maxSumEndingHere > maxSumSoFar), maxSumSoFar = maxSumEndingHere.

So in this approach, we can use a single loop and two extra variables. This means there is no need for O(n) space or double traversal. So Kadane's algorithm is an optimized solution idea of the maximum subarray sum problem.

Solution steps

1. We initialize variables maxsumSoFar and maxsumEndingHere with X[0].

2. Now we run a loop from i = 1 to n - 1. At each ith iteration:

   • We calculate the max subarray sum ending at the ith index, i.e., maxsumEndingHere = max (maxsumEndingHere + X[i], X[i]).
   • We also update maxsumSoFar, i.e., if (maxsumSoFar < maxsumEndingHere), maxsumSoFar = maxsumEndingHere.
3. By the end of the loop, the maximum subarray sum value gets stored in the variable maxSumSoFar. We return this value as the output.

Solution code C++

int findMaxSubarraySum(int X[], int n)
{
    int maxsumSoFar = X[0];
    int maxsumEndingHere = X[0];
    for (int i = 1; i < n; i = i + 1)
    {
        maxsumEndingHere = std::max(maxsumEndingHere + X[i], X[i]);
        if (maxsumSoFar < maxsumEndingHere)
            maxsumSoFar = maxsumEndingHere;
    }
    return maxsumSoFar;
}

Solution code Python

def findMaxSubarraySum(X, n):
    maxsumSoFar = X[0]
    maxsumEndingHere = X[0]
    for i in range(1, n):
        maxsumEndingHere = max(maxsumEndingHere + X[i], X[i])
        if maxsumSoFar < maxsumEndingHere:
            maxsumSoFar = maxsumEndingHere
    return maxsumSoFar

Time and space complexity analysis

We are traversing each element using a single loop and performing a constant operation. So time complexity = O(n). Since we are using a constant number of variables, space complexity = O(1).

Critical ideas to think!

• How can we modify the above approaches to find the start and end indices of the subarray with the maximum sum?
• Do the above algorithms handle the case of negative numbers?
• Can we think of solving this problem using other approaches?
• How can we design a solution to calculate the maximum sum submatrix of size k x k in the m x n matrix?
• How do we solve the problem if a sorted array is provided as an input?

Comparison of time and space complexities

• Three nested loops: Time = O(n^3), Space = O(1).
• Two nested loops: Time = O(n^2), Space = O(1).
• Divide and conquer: Time = O(nlogn), Space = O(logn).
• Dynamic programming: Time = O(n), Space = O(n).
• Kadane's algorithm: Time = O(n), Space = O(1).

Suggested coding questions to practice

• Find the maximum product subarray
• Find the sum of the maximum elements of every possible sub-array
• Find the longest subarray in a binary array with an equal number of 0s and 1s
• Find the largest sum contiguous subarray having only non-negative elements
• Product of array except self
• Max consecutive ones
• Number of buildings facing sun

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!