Maximum sum subarray

#1

how is dp is used in this I didn’t get it please clear it…

#2

Here u can use dp by assuming that if we know the maximum subarray sum till index i-1 then at index i maximum sum can be max(dp[i-1]+a[i],a[i])

#3

it would be dp[i-1] i think in place of a[i]?? correct me if i am wrong

#4

I am calculating maximum subarray sum ending at index i. Remember that array can have negative elements. The answer is maximum of all dp[i] where i is from 0 to n-1.

#5

so it should be max(do[i-1]+arr[i],dp[i-1])

#6

consider the case 2 -3 5 4 here 5 is greater than 2+(-3) so it is max(dp[i-1]+a[i],a[i])

#7

Can you tell. Me what are the overlapping subproblem here in this problem so that i can understand it better because I am not able to figure it out what is exactly the subproblem which is repeating and we are using dp…

#8

Can you clear it???

#9

just consider 3 4 7 3+4=7 then if we know the answer of 7 before then we can get the answer of 7 ahead

#10

Can you tell. How can we do it by top down?? By memoization??

#11

I have told the recursive case already above.

#12

Can you send the code of top down??

#13

hello sir please clear this doubt…

#14

Where are u facing problem?

#15

Sir it’s been 8 days… I have done this problem… You are replying after 8 days??