Hi guys can someone please help me out. I’m getting correct output for the sample input but still getting WA.
https://www.codechef.com/viewsolution/33436238
Thanks.
How did you even come up with this? There are more cases that this program will get wrong than right. Why sum - 1? How does the sorting relate to the fact that you have to go right or stay on the same column?
I tried solving some cases myself both sorted and unsorted and I noticed that answer was always 1 less than that from the sorted array. So sum-1 
. Also, I’m new to this 
I mean… any case where all the numbers are equal
1 Like
Yeah in that case it fails. Thanks.
your algorithm is wrong, the max sum is not directly add the max one in each row. has many other cases. This is a DP problem
let’s say starting row x = 0, y = 0 then → next row (either go down directly (x + 1, y) or down right (x + 1, y + 1)), after go to the final row, you need to figure out the max sum.
My DP Solution:
generate a 2D DP array, dp[i][j] save till current row, the max sum, so the answer is the max of the final row.
to update dp[i][j], needs previous max sum from top dp[i-1][j] or top left dp[i-1][j-1], plus current g[i][j]
so: dp[i][j] += g[i][j] + Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
case condition, first col j == 0, only from dp[i-1][j], top left is out of bound
so dp[i][j] += g[i][j] + dp[i - 1][j];