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.
