Max sum subarray using suffix matrix

#1

i understand the approach to find the maximum sum of the array by using suffix matrix approach we have to solve and sir said we have to start sum up the elements from bottom right but i am facing difficulty in creating array indexing while making the loop

02b97665-194b-479c-a201-d9b1cc5a8c36.png1366×768

#2

Hi Dipesh, pls save ur code on ide and send… also pls explain what difficulty are u exactly facing…

#3

ok sir i send u my code on ide my doubt is how to indexing for suffix sum matrix as sir said in the lecture that for a given matrix prepare suffix matrix and max of that is the answer

#4

https://ide.codingblocks.com/s/623806 sir this is my code

#5


I have corrected ur code… its giving correct suffix sum array now…

#6

sir it is prefix sum i guess because in the lecture sir said suffix sum array we have to start from bottom right means last row ka last element same rahega then we have to start adding in reverse direction and the code u corrected will perform sum in forward direction only

#7


i hope it would clear ur doubts… i have reversed the things…

#8

to find the maximum element in suffix matrix we apply kadens algo because final answer too vohi hogga

#9

kadanes in 1d and 2d arrays are different

#10

sir in the same question i have doubt that to find the maximum of suffix matrix what aaproach we have to follow

  1. iterate over the complete matrix and keep the pointer of maximum value
  2. or kadanes algo
#11

ya… since u have ur suffix matirx with u, u can just iterate over and find max value…

#12

shall i mark it as resolved??

#13

yes sir thanks for the help

#14

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.