I have seen this problem recently and it was asked in directi hiring challenge. You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum. You can only choose consecutive toffee packets to put in a box. Input The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains two space separated integers N, M denoting the number of toffee packets and the number of boxes respectively. The second line of each test case contains N space separated integers c1, c2, ..., cN where ci denotes the number of the toffees in the ith toffee packet. Output For each test case, output a single line containing the maximum number of toffees in a box. Also, output 1 if such an assignment of toffee packets to boxes is not possible. Constraints 1 ≤ T ≤ 20 1 ≤ N,K ≤ 100000 1 ≤ ci ≤ 1000 Example Input: 1 4 2 10 3 5 7 Output: 13 Explanation Below are the possible assignments of toffee packets to boxes. 10 [3 5 7] 10 3 [5 7] 10 3 5 [7] For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13 I am not able to get any idea how to solve this.Please suggest a solution so that i can understand. asked 28 Jul '16, 11:50
