Do we really need Kadane’s Algorithm?

Question: Find the sum of contiguous subarray within a one-dimensional array of numbers that has the largest sum.

For those of you who are new to this question, there is an algorithm that is used to solve this question.

Let us go through that first.

Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0)
            max_ending_here = 0
return max_so_far

Explanation:

The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Can we do it with any other method with the same time complexity?

Yes!

Let’s see how

Maintain 2 pointers, p1 and p2. p1 signifies the start of our subarray and p2 the end of the subarray. Set sum=0 and keep on incrementing the p2 counter until it reaches the end of the array. If the sum goes negative in any iteration then increment p1.

#include <bits/stdc++.h>
using namespace std;
int n,ans=0,p1=0,p2=0,sum=0,a[100];
int main ()
{
    cin>>n;
    for(int i=0;i<n;i++)    cin>>a[i];
    while(p2!=n){
        sum+=a[p2];
        while(sum<0)  {
            sum-=a[p1];
            p1++;
        }
        p2++;
        ans=max(sum,ans);
    }
    cout<<ans<<endl;
    return 0;
}

Discord link: https://discord.gg/zEHhKWQm for any questions, debugging sessions.