I recently attended HackWithInfy Round 2 and this was one of the questions they asked.

You are given N blocks consisting of integers. The blocks are one-dimensional arrays. You want to put them all in the box of length

M in such a way that they do not overlap. To do this work, you are

allowed to remove any number of leftmost or rightmost elements in

some blocks. You can also remove a block completely or cannot remove

anything at all.

What is the maximum sum of elements that you can put in the box?

Note: You cannot leave some free space in the box.

Input Format

The first line of input contains two integers N and M denoting the number of blocks and length of the box respectively.

The next N lines describe the blocks. The first number in the i-th of these lines is len, denoting the length of the i-th block. Then, len-i integers follow denoting the elements of the i-th block.

Output Format

Print the maximum sum of elements that you can put in the box.

Constraints

1 <= N <= 100

1 <= M <= 1000

-10^9 <= elements of the block <= 10^9

0 <= sum of overall len-i <= 10^5

Sample Input

3 4

3 2 3 5

2 7 -1

2 8 10

Sample Output

30

Explanation

Sonya has three blocks: {2, 3, 5}, {7, -1}, {8, 10} and a box of length 4. The best strategy is:

delete two leftmost elements in the 1-st block {2, 3, 5} => {5}

delete the rightmost element in the 2-nd block {7, -1} => {7}

Now the blocks look like: {5}, {7}, {8, 10}, and Sonya can put them all in the box. The sum of elements in the box is 30.

I was trying dynamic programming approach but were not able to complete the solution. If anyone able to solve it, please share it here.

I tried solving this using dynamic programming.

Approach:

- For each input array[i] of size[i] for all (0 <= i < N), try find an another array where at each index, the value will have the maximum of continuous sum of elements of length j of array[i], for all (0 <= j < min(m, size[i])).

Eg. let array = {2, 3, 5}. Then new-array will be {0, 5, 8, 10}.
- Now create an auxiliary array ans[m+1], initialized with 0.
- Now iterate over each newly created array an try updating the ‘ans’ array accordingly.

Explanation of given example:

For array[0], the new array is { 0, 5, 8, 10 }. Then ‘ans’ array will be { 0, 5, 8, 10, 0 }.

For array[1], the new array is { 0,7, 6 }. Then ‘ans’ array will be { 0, 7, 12, 15, 17 }.

For array[2], the new array is { 0, 10, 18 }. Then ‘ans’ array will be { 0, 10, 18, 25, 30}.

So our result will be max_element of ‘ans’ array.

Time Complexity analysis: For all N, we iterate over each array of size[i] and find another array of size = min(m,size[i]) which is O(N * M * min(M,size[i]) ), roughly 1e8.

I’m still looking for a better approach. Thanks

**Update: I got selected in the top 100. Hence I think this solution worked.**

Mine approach is similar to your. I also use dp[i][j] = max sum of length j ( continuous) at the i the block but Complexity to fill this dp was large Since each entry take O(size of block ) time. Then initialized an array int pointer[n] which initially store 0 (basically points to zero size blocks inclusion to ans from all block 0 to n - 1) and then I start including elements seeing which one add max to final_ans. I also used max heap to do so where I push dp[i][j + 1] - dp[i][j] . Initially heap store dp[i][1] - dp[i][0] for each 0 < i < n.

One more thing : I test on the custom input when I put the m == sum of size of all blocks, then that the expected output was wrong even though the actual output for this case is simple because all element get included and ans = sum of all element. But still It was different.

That’s why I took maximum_element of my final answer array and not ans[m] as result.