my code https://ide.codingblocks.com/s/38895
ques https://hack.codingblocks.com/contests/c/526/1098
i have followed divide and conquer approach in this and then optimized it using DP just like we did it in the case of max subarray sum (using D and C) but it is showing WA for 2 test cases
What’s wrong in this and what other approach can be followed
Hi Naman !
There is no need of DP optimisation , you can just iterate over the array with one variable and keep updating your answer (subarrray product) and whenever you touch the element zero set the temporarry variable to 1 .
For more clarification , go through this code -->
https://ide.codingblocks.com/s/40066
sir why have u traversed the array twice, from starting as well as end.
and why have u maintained two ans
@kathuria There can be two cases (i) it contains doesnt element as 0 , if it is the you just need to find the maximum subarray product
Now , for finding maximum subarray product , you can think of the way that -> traverse the array and keep checking for maximum product just like kadane maximum subarray sum .
(ii) it contains 0 as element , then you have to find maximum product in the same manner as discussed above but whenever you hit 0 then your max answer can’t be increased as it will contain zero so initialise your temp variable as 1 and then start finding your answer from the index just greater than the index of zero,
It;s easy to understand . If you have still any doubt then feel free to ask.