How to get to know that the sum is taken only for elements placed at contiguous locations. In my code, it will take the sum of entire array excluding first element.
Solving MaxSumSubarray using recursion
hello @PThak2018
this is not the correct code of kadane.
in some cases it might return sum of non contiguos element.
Exactly.
Need to understand how to ensure it is taking contiguous elements only using recursion.
Understood kadane algorithm but need to clear recursion approach.
ok for that u need to declare one global variable which will store actual maximum.
in recursion if small output is comming out negative then dont take its contribution and return a[i] only
otherwise update ur global variable i.e global=max(global,a[i]+smalloutput)
and return a[i]+smalloutput
Sorry Aman.
Didn’t get it. Can you add this condition or elaborate?
check this- > https://ide.codingblocks.com/s/252138
i dont know java much so cant help u with syntax errors.
Thanks Aman.
Only thing is max value needs to be updated for both cases(smalloutput<0 && >0). Now the code is working perfectly fine on local and other IDEs.
But it is giving run error while submitting on hacker blocks. Can I get to know somehow what is the run error?
What could be the reason for the same?
see u can do that but this will not create any difference because if u recall kadane iterative version there also we use to ignore the subarray if its sum get negative.
run error occurs because of following reasons->
- division by zero
- performing an operation on incompatible types
- using an identifier which has not been defined
- accessing a list element, dictionary value or object attribute which doesn’t exist
- trying to access a file which doesn’t exist
Hi Aman,
In Kadane, we used to update our max based on the currentSum even if it comes as -ve and make currentSum as 0 when it’s value becomes less than 0.
In Recursion approach, updating count value is required in both the cases. Below is the code with a running test case because of which I believe count needs to be updated every time. Have a look.
Correct me If I am going wrong.
no nothing wrong in that .
