getting WA on some hidden test case. couldn’t debug, please help!
bottom up approach is pretty intuitive for this question.
my solution for this: https://codeforces.com/contest/1350/submission/79866394
Ok I made some changes to your submission. (I am using maxi as 0 instead of 1)
the longest subsequence dp value will store actual answer -1 so I am adding +1 at the end.
The most important thing is (due to which I was also getting ton of WA at test 2 while debugging)
The recursive approach is different from iterative approach.
Submission #79989773 - Codeforces -My iterative solution
Submission #80037925 - Codeforces -Your recursive code with changes.
The iterative solution works in a manner that ends up storing the longest subsequence value which ends at that element. (So at the end of calculating dp values we simply take the max of them)
The recursive approach does the opposite it stores the longest subsequence which begins on that element and therefore we need to run the recursion for every element and thereafter take the max of their values returned.
You had a base condition missing if (2*n>ar_size return 0;)
Hopefully this made some sense.
2 Likes
Thank you so much, I was lost for hours on this. only if i could give you more than 1 like.