Kadane's algorithm

#1

How to find out lower and upper bound of subarray having maximum sum in Kadane’s algorithm

#2

just make 2 variable l and r
and update them accordingly

look at kadane function

int kadane(int a[], int n) 
{ 
    int ans = 0, currSum = 0; 
    int i; 
    int l=0,r=-1;
    int t=0;
    for (i = 0; i < n; i++) 
    { 
        currSum = currSum + a[i]; 
        if (currSum < 0) {
            currSum = 0; 
            t=i;
        }
        if (ans < currSum){ 
            ans = currSum; 
            r=i;
           l=t;
        }
    } 
    for(int x=l;x<=r;x++){
       cout<<a[x]<<" ";
    }
    return ans; 
}

i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved :grinning:
if you have more doubts regarding this feel free to ask

#3

I didn’t get your code

#4

which part is not clear

it is simple kadane’s algorithm
only change i made is used two variables l and r
to print max subarray

have you know kadane’s algorithm??

#5

once have look at https://ide.codingblocks.com/s/286190

#6

modified code

i have done some small changes
look at that

#7

why is l = i+1 in line no. 17. why not l = i?

#8

because when you set cs=0
means for next onwards you start your new subset
so l should be i+1 not i

#9

i hope this helps
don’t forgot to mark doubt as resolved :grinning:
if you have more doubts regarding this feel free to ask

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.