Can someone help me find mistake in my code?

Блог пользователя VandanRogheliya

Автор VandanRogheliya, история, 4 года назад, По-английски

While solving this question I came up with this solution. I was getting WA. I checked my code 5 times, I was not able to find a mistake. Then Finally I checked the editorial, it was the same dp but in an iterative form. Can someone point out the mistake?

VandanRogheliya
4 года назад
6

Комментарии (6)

Написать комментарий?

spookywooky

4 года назад, # |

I think this line is wrong else Max = max(Max, recFun(dp,j));. Why is it there?

i.e. Let $$$P_{smax}$$$ be the position of the max S values. If this is in the first half of the array you will have $$$dp[P_{smax}]=2$$$ at some point of time, which is not correct.

→ Ответить

VandanRogheliya

4 года назад, # ^ |

If I do not put else Max = max(Max, recFun(dp,j)); then for the test cases where $$$s[0]$$$ is not included will fail.

And I did not get your 2nd point. You are trying to say if max from array S is in the first half then code would fail? If so, I checked, the code works for that test case.

→ Ответить

spookywooky

4 года назад, # ^ |

I modified your code, this works. 80869160

Still I think the else Max = max(Max, recFun(dp,j)); is wrong. Imaging s[100] there is the max value of all s[]. At dp[200] there is some value!=1, say 42. In this case you will have dp[100]=42, too. And mayby dp[50]=43, what is completly wrong.

So, after I removed that line it still not worked. The reason is that then not all dp states get calculated. Imagine the max s[] value at idx=1, then there is no recusion at all. So I changed the code that the recFun() is called for every index starting at n backwards to 1.

→ Ответить