Maximum Subarray Sum | Kadane’s Algorithm | Array

Kadane’s Algorithm is one of the simplest algorithm in computer programming.The problems of kadanes’s algorithm is frequently asked on coding interviews and various programming contests.

This is the first post of the Kadane’s Algorithm series and I will discuss about some of the problems in this series. Before going to solve some of the array problems using kadane’s algorithm we have to know about kadane’s algorithm.

Kadane’s algorithm is a famous algorithm used to find the maximum subarray sum within a given array of numbers. It was developed by computer scientist Jay Kadane in 1984. The algorithm operates in a linear time complexity, making it an efficient solution for this problem.

Here’s an explanation of Kadane’s algorithm:

1. Start by initializing two variables, mxSum and sum, to the first element of the array. These variables will keep track of the maximum sum encountered so far and the maximum sum ending at the current position, respectively.
2. Iterate over the array from the second element to the last element.
3. At each iteration, update sum by taking the maximum value between the current element and the sum of the current element and sum. This step essentially determines if extending the subarray to the current position results in a larger sum than starting a new subarray at the current position.
4. Update max by taking the maximum value between mxSum and sum. This step ensures that max always stores the maximum sum encountered so far.
5. Repeat steps 3 and 4 until the entire array is traversed.
6. Finally, the value of mxSum will represent the maximum subarray sum.

Here is the code in C++ :

int maxSubarraySum(int arr[], int n)
{
    int mxSum = arr[0],sum = arr[0];
    for(int i=0;i<n;i++){
        mxSum = max(sum+arr[i],arr[i]);
        ans = max(ans,sum);
    }
    return mxSum;
}