Hello, asked 30 May '18, 09:07

answered 30 May '18, 12:45
This problem uses similar approach like LIS O(n^2) version
(30 May '18, 12:50)
Thanks for the response, but can u point out the mistake in my code?
(30 May '18, 13:50)
Yes! If you give me your recursion formula.
(30 May '18, 14:43)
I have posted the links in question. Here they are once again:
(30 May '18, 16:49)
If i'm not wrong for each j you may need to find two optimal(means they are best choice for cost) index i1 < i2 < j such that frameSize[i1] < frameSize[i2] < frameSize[j] and this will lead to O(n^3) time complexity.I'm still not able to find the transition function from one state to another state.
(30 May '18, 20:38)
I guess my solution is completely wrong. Thanks for all the time and effort :)
(30 May '18, 21:17)
showing 5 of 6
show all

Hey! Dishant in your dp you need to make cache[pos][last][second_last] as it might come to pos last with second last chosen or different from before or even not chosen So although answer will be different your code will return the same value. But if you make the dp as I told it would give tle (as it would be O(n^3)) so you should do something like meet2mky said Here is my code  http://codeforces.com/contest/987/submission/38740788 EDIT : Example test case consider the input Sorry for bad english answered 30 May '18, 17:48
