Wrong output for the given test case in kadanes algorithm

#1

for test case

###4
######-1 -2 -3 -4

//kadanes algorith to print maximum sum of an subarray in o(n)
#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[1000];
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    int cur_sum=0;
    int max_sum=0;
    for (int i = 0; i < n; i++)
    {
        cur_sum+a[i]<0?cur_sum=0:cur_sum+=a[i];//whenevr current sum is <0 we make cursum=0
        max_sum=max(max_sum,cur_sum); 
    }
    cout<<"Maximum sum is : "<<max_sum;
    return 0;
}
#2

The first test case where code failed:

Input:
4
-1 -2 -3 -4

Its Correct output is:
-1

And Code’s output is:
0

#3

hello @sagar_aggarwal
a) intialise this with a[0]

b)

here use following condition
cur_sum=max(cur_sum+a[i], a[i]) ;

#4

i didn’t got this. can you show me the exact code. because i have implemented the code as teached in the video

#5

@sagar_aggarwal
check this->

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[1000];
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    int cur_sum=0;
    int max_sum=a[0];
    for (int i = 0; i < n; i++)
    {
        cur_sum=max(cur_sum+a[i],a[i]); 
        max_sum=max(max_sum,cur_sum); 
    }
    cout<<"Maximum sum is : "<<max_sum;
    return 0;
}
#6

can you explain this more

#7

instead of making current sum 0 (for negative case) we are keeping it a[i] so that we can handle negative case as well .
that syntax is doing the same thing.

#8

IS this okay?

//kadanes algorith to print maximum sum of an subarray in o(n)
#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[1000];
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    int cur_sum=0;
    int max_sum=a[0];
    for (int i = 0; i < n; i++)
    {
        cur_sum=cur_sum+a[i];
        max_sum=max(max_sum,cur_sum);
        if (cur_sum<0)
        {
            cur_sum=0;
        }
         
    }
    cout<<"Maximum sum is :"<<max_sum;
    return 0;
}
#9

yeah it is correct…

1 Like