How is this any different from kaden's algorithm?

#1

In this problem (Maximum subarray sum DP problem), sir has used botttom’s up approach to solve it. i.e he has used a loop to traverse and then keep track of max sum and just as we do in kaden’s algorithm, he has implememnted the DP solution. My doubt is that, how is this solution any different than the Kaden’s algorithm?

Also, is there a top down recursive solution to this problem? if yes, please share the code

#2

hello @anshufirefox
kadane is based on this dp solution only.

only difference is in kadance we were using a single variable to keeptrack of the cummulative sum, here we are using an array(dp).

yeah we can do that


int solve(int i ) { //it will give maximum sum we can get starting from index i
  complete this function on ur own
}



int mx=0;
for(int i=0;i<n;i++){
     mx=max(mx,solve(i));

}
#3

I tried to complete the code but could not complete it on my own, would you please share the full code of the Top down approach.

#4 
int a[n];
int dp[n];
int solve(int i ) { //it will give maximum sum we can get starting from index i
  int sum=0;
if(i>=n){
  return 0;
}
   if(dp[i]!=-1)
     return dp[i];
    
  int ans=0;
  ans=max(a[i], a[i]+solve(i+1) );
  
return dp[i]=ans;
   
}



int mx=0;
for(int i=0;i<n;i++){
     mx=max(mx,solve(i));

}
#5

where is the main() function?

#6

bro try to write on ur own.
and put this inside main->



int mx=0;
for(int i=0;i<n;i++){
     mx=max(mx,solve(i));

}

and the solve functionn above the main

#7

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.