Maximum Subarray Sum: Kadane’s Algorithm

   October 27, 2022

Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

(https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1)

This question can also be solved with brute force, which will give a time complexity of O(n^2), to improve this solution we will use kadane’s algorithm and which can be used to improve the time complexity.

Brute Force approach to find Maximum Subarray Sum

Let’s take an example array:

Kadane's Algorithm Maximum Subarray Sum: Kadane's Algorithm Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

In this example, the whole array sum is the maximum sum, i.e., 9

Kadane's Algorithm Maximum Subarray Sum: Kadane's Algorithm Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

One very obvious but not-so-good solution is to calculate the sum of every possible subarray and the maximum of those would be the solution. We can start from index 0 and can calculate the sum of every possible subarray starting with A[0] as shown in the figure.

Kadane's Algorithm Maximum Subarray Sum: Kadane's Algorithm Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

Note: Every element of the array is also a subarray.

Code for Maximum Subarray Sum using Brute force approach:

long long maxSubarraySum(int arr[], int n){
    int sum = INT_MIN;
    for(int i = 0;i<n;i++)
    {
        int s = 0;
        for(int j = i;j<n;j++)
        {
            s+= arr[j];
            sum = max(sum, s);
        }
    }
    return sum;
}

Here, we declare sum as global sum and s and local sum. The local sum is used to calculate the sum of every subarray and the global sum is used to calculate the max sum of all local sums.

For each element, we declare our local sum as 0 and keep adding later elements to the local sum, after adding each and every element we update our global sum with the max of the local sum.

The problem is this solution takes O(n^2). The array of very long-size computations will be very complex as the number of subarrays will increase rapidly.

Kadane’s Algorithm

The optimized solution for the given problem is kadane’s algorithm.

What kadane’s algorithm actually says, every element has two choices:

  1. It can be a part of a subarray with the last elements or elements.
  2. It can start a new subarray including the element itself.

How to decide which one to choose?

We check if the sum before the element is less than the current element we start the new subarray with that element.

Kadane's Algorithm Maximum Subarray Sum: Kadane's Algorithm Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

Let’s take the array shown above as an example.

We will traverse the array and will see how the algorithm works after that we will go through the code.

For i = 0,
We have no other element so our sum will be -5.

For i = 1,
arr[i] = 1,

For 1,
we have two choices either we consider -5 + 1 or only 1, as 1 > -5, we consider 1.

For i = 2,
arr[i] = -2

For -2,
we have choices -5 + 1 + -2, 1 + -2 and -2 among all these -1 is the greatest and if we look closely it is last greatest sum + arr[i].

For i = 3,
arr[i] = 3

We can have either -1 + 3 or only 3, 3 > 2, we will update our sum as 3.

Similarly going on we will find our greatest sum as 4.

Code to find the Largest sum contiguous subarray or Maximum Subarray Sum using Kadane’s Algorithm:

long long maxSubarraySum(int arr[], int n){
    
    int res = arr[0];
    int maxEnding = arr[0];
    for(int i=1;i<n;i++)
    {
        maxEnding = max(maxEnding + arr[i], arr[i]);//updating value of sum
        res = max(res, maxEnding);//updating largest value
    }
    
    return res; //returning value
}

Conclusion

In this article, we learned how to solve the Maximum Subarray Sum in O(n) time complexity and also what is kadane’s algorithm and how it can make calculations very easy.

Best 100+ Python Projects with source code

Also Read:

Share:

Author: Ayush Purawr