https://www.hackerrank.com/contests/pasc-dp/challenges/contiguous-maximization My approach to this problem was to calculate maximum sum of each length sub-array's of each row separately and then use the length as weight and sum as price make it work like the way knapsack works. But issue is that i'am facing wrong answers in large test cases and not able to figure out why am i getting WRONG ANSWER. Any help would be really helpful
My submission
You should understand that competitive programming isn't always about trying to convert the problem to the most classical problem you know, but rather applying the concepts you learn from solving classical problems to the new one. Why doesn't your approach work? Simply because it opens the possibility of taking multiple segments or even multiple of the same item from the same row, which is clearly forbidden. What should you do instead?
Let $$$dp[i][j]$$$ represent the maximum attainable sum from the first $$$i$$$ days with $$$j$$$ lectures already attended. Transition is as straightforward as it gets:
$$$dp[i][j] = \max\limits_{0 \le sz \le M} dp[i - 1][j - sz] + f(i, sz)$$$
where $$$f(i, sz)$$$ represents the maximum sum of a contiguous subarray of size $$$sz$$$ on day $$$i$$$. Hopefully you are capable enough to implement this in $$$O(NM^2)$$$.
Your rating graph is motivational <3