Sumanto's blog

By Sumanto, 4 years ago, In English

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
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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?

  1. Maybe read the editorial whose sole purpose is to help you in these situations
  2. Read the short summary I will provide below

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)$$$.