I am solving this question from codeforces…
This is the question…
https://codeforces.com/problemset/problem/1406/B
I want to come up with dynamic approch…
for which i have written the recursive code… But this recursive code is showing wrong answer… Please check this…
This is my code…
Thanks
Getting wrong answer
hello @ashishnnnnn
ur logic is correct.
to solve it using dp.
ur dp states should be
dp[i][cnt] = maximum product when u need to pick cnt number of elements and when u r considering array [i…n-1]
No…it is showing wrong answer… Some mistake is there in recursive code…
pls mention any test case where is giving wrong result and what is correct output
4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1
This is the test case given in question…
Here for 2nd and 4th test case…it is showing wrong answer
. … … … …
This is correct output…
-120
12
0
945
and this is this code output…
-120
-6
0
270
a) in base case u cannot return 1.
it should be return le==0;
b) return max(a,b) ; is not correct negative numbers can also contribute to the answer.
ur function should return pair<int,int> where one stores answer when u have ignored current and one stores answer when u have included current
then what should i return at the base case…
When i>=n or le==0 …these are the two base case…so when we return pair… At that time what should we return in base case…
in one return answer of le==0 and in one simply return 0
check this implementation ->
Hii… Can you explain …In short the logic …behind the this…
This is one approch i come up with… But it is showing wrong answer in test case-3
The code… you have shown… How will we memoize this… It will take 3d dp… and ans value can increase upto very high
i thought u r familar with this technique.
what i m doing is -> i m generating all subset and then picking maximum answer from them.
Can you see my submission … Where my code is wrong…
Plese… Review my code… I think i have come up with correct approch… Don’t know where i am missing…