I have created a page Facebook where I have posted the explanation of the first 3 problems of the DEC2016 contest. I didn’t manage to do the others. If I succeed I’ll post their explanation too
Feel free to like my page, to receive updates on it
I felt that your example for the editorial of KIRLAB was wrong or I may have misunderstood it. Let’s try your method with the given test case.
13 2 8 6 3 1 9
here dp[13]=1, dp[2]=3 and dp[3]=3. If the answer is max(dp[i]) then the answer should have been 3 whereas the answer is 5.Please comment on this @codedecode0111. Forgive me if I may have misunderstood it.
Hello @tej_17: We check the elements sequentially, so first element we check is 13, then 2, 8 and so on…
So, initially, dp[i] = 0 for all i.
Case 13:
dp[13] = 0, so we update dp[13] = 1
Case 2:
dp[2] = 0, so we update dp[2] = 1
Case 8:
dp[2] = 1, so we update dp[2] = 2
Case 6:
dp[2] = 2, dp[3] =1, max = 2, so we update dp[2] = dp[3] =2 +1 = 3
Case 3:
dp[3] = 3, so we update dp[3] = 4
Case 1 :
We skip.
Case 9:
dp[3] = 4, so we update dp[3] = 5.
Max(dp[i] for all i) is 5 which is the required answer.