How should i write a recusive solution for this problem, i have seen its editorial but its not clear to me, can anyone please help me …??
Hi - which part specifically are you having trouble with? If it’s the “recursive” part of “How should i write a recusive solution for this problem”, I’d say “You shouldn’t” - this problem can be neatly dealt with using iteration.
Hopefully you can see my code and find it clearer than the Editorial:
“newMaxValueEndingAtTop” is, at the end of the ith iteration, the maximum value that can be formed of the first i elements where the last element is b[i]; “newMaxValueEndingAtBottom” is the maximum value that can be formed from the first i elements where the last element is “1” (“b[i]” and “1” are the only elements worth considering - there’s a sketch proof of this in the long, un-proof-read comment in my submission) You can probably transform that recurrence relation from an iterative one to a recursive one with little effort
Thanks your solution helped me alot and i wanted to write a recursive solution just because i was not getting the DP solution
Great; glad it was of some use