Divide Chocolates
Ninja bought chocolate consisting of some chunks. The sweetness of each chunk is given in an array ‘ARR’. Ninja has ‘K’ friends, and he wishes to divide the chocolate into 'K' + 1 cut with some consecutive chunks. He wants to divide the chocolate into chunks under the condition that he will take the piece that has the minimum total sweetness.

He is very busy doing other stuff. Can you help him to maximize the total sweetness of the part that you will get under the given condition?

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow. The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the size of array ‘ARR’ and the number of friends Ninja has. The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array ‘ARR’.

Output Format:

For each test case, print the maximum sweetness that Ninja can get under the given condition. Print the output of each test case in a new line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Divide Chocolates

Ninja bought chocolate consisting of some chunks. The sweetness of each chunk is given in an array ‘ARR’. Ninja has ‘K’ friends, and he wishes to divide the chocolate into 'K' + 1 cut with some consecutive chunks. He wants to divide the chocolate into chunks under the condition that he will take the piece that has the minimum total sweetness.

He is very busy doing other stuff. Can you help him to maximize the total sweetness of the part that you will get under the given condition?

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the size of array ‘ARR’ and the number of friends Ninja has.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array ‘ARR’.

Output Format:

For each test case, print the maximum sweetness that Ninja can get under the given condition.

Print the output of each test case in a new line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1<= T <= 10
1 <= N <= 50000
0 <= K < N
1 <= ARR[i] <= 10000

Where 'ARR[i]' is the sweetness of the ‘i_th' chunk.

Time Limit: 1 sec

Accepted Answer

Dynamic Programming

The idea is to figure out the recursive calls and optimize them using dynamic programming.

It breaks down into a problem of dividing the array into ‘K’ + 1 partitions such that the partition which has the lowest sum of sweetness is maximum as compared to all the possible partitions. It’s better to make a prefix array as we would need the prefix sum of the array in every iteration.

Now, we will start from the bottom, and then we will find the final answer. We will find the answer for breaking the subarray from indices from 0 to ‘i’ into ‘j’ parts where ‘i’ lies from 0 to ‘N’ - 1 and ‘j’ lies from 0 to a minimum of ‘M’ and ‘i’ + 1.

There is a base condition: If the number of chunks is less than the number of desired divisions, then Ninja won’t get any chunks. So, the answer will be 0.

The steps are as follows:

Base Condition: If ‘K’ is greater than or equal to the number of chunks in the array ‘ARR’, return 0.
Increment ‘K’ by 1 as there are ‘K’ friends and the number of partitions expected is ‘K’ + 1.
Calculate the prefix sum of the given array and store it in an array ‘PREFIXSUM’ as we will require it in every iteration. Otherwise, it will increase the time complexity.
Initialize a matrix ‘DP’ with the number of rows = ‘N’ and the number of columns = ‘K’ + 1 to the minimum integer value. In this matrix ‘DP[i][j]’ stores the sweetness of the part whose sum of sweetness is minimum after dividing the subarray from indices 0 to ‘i’ into ‘j’ parts. So, for any ‘i’, the 0'th part is not used for all ‘i’ in the range 0 to ‘N’ - 1.
Iterate from ‘i’ = 0 to ‘N’ - 1 and fill the first column with the prefix sum of the respective indices.
Iterate from ‘i’ = 1 to ‘N’ - 1:
- Iterate from ‘j’ = 2 to a minimum of ‘K’ and ‘i’ + 1:
  - Now, we will break the subarray from indices ‘0’ to ‘l’ into ‘j’ - 1 part and then ‘l’ + 1 to ‘i’ into 1 part for all ‘l’ in the range 0 to ‘i’ - 1.
  - Iterate from ‘l’ = 0 to ‘i’ - 1:
    - Store the value of prefix sum from ‘l’ + 1 to ‘i’ + 1 in a variable ‘TEMP’.
    - Update the value of ‘TEMP’ to the minimum of ‘TEMP’ and 'DP[l][j-1]'.
    - Update the value of ‘DP[i][j]’ to the maximum of ‘DP[i][j]’ and ‘TEMP’.
Return ‘DP[N-1][M]’ as the final answer as this is the answer for breaking the array arr from 0 to ‘N’ - 1 into ‘M’ parts.

Space Complexity: OtherExplanation:

O(N*K), where K denotes the number of friends and N is the number of chunks.

As we are using a 2D matrix of size N*(K+1) to store the results for breaking the subarray from indices 0 to n - 1 into K parts. Hence, the overall space complexity is O(N*K).

Time Complexity: OtherExplanation:

O((N^2)*K), where ‘K’ denotes the number of friends and ‘N’ is the number of chunks.

As we are iterating over all the elements and then creating all possible divisions from 2 to ‘K’ and then choosing the maximum answer from all the possible divisions from 0 to ‘i’ - 1. Hence, the overall time complexity is O((N^2)*K).

Java (SE 1.8)

/*

	Time Complexity: O((N^2)*K)

    Space Complexity: O(N*K)



    Where 'K' denotes the number of friends and 'N' is the number of chunks.



*/



import java.util.ArrayList;



public class Solution {



	public static int getMaximumSweetness(ArrayList arr, int k) {

        int n = arr.size();



        // Base Condition.

        if (k >= n)

        {

            return 0;

        }

    

        // As the number of division is 1 + 'K'.

        k++;

    

        // Making the prefix array to store the sum of individual sub arrays.

        int[] prefixSum = new int[n + 1];

    

        for (int i = 0; i < n; i++)

        {

            prefixSum[i + 1] = prefixSum[i] + arr.get(i);

        }

    

        /*

            Matrix to store the sweetness of the part whose sum of sweetness 

            is minimum after dividing the subarray from indices 0 to 'i' into 'j' parts.

        */

        int[][] dp = new int[n][k + 1];



        for(int i = 0; i < n; i++) {

            for(int j = 0; j <= k; j++) {

                dp[i][j] = Integer.MIN_VALUE;

            }

        }

    

        for (int i = 0; i < n; i++)

        {

            dp[i][1] = prefixSum[i + 1];

        }

    

        for (int i = 1; i < n; i++)

        {

            for (int j = 2; j <= Math.min(k, i + 1); j++)

            {

                /*

                    Breaking the subarray from indices 0 to 'l' into 'j' - 1 parts

                    And then 'l' + 1 to 'i' into 1 part for all 'l' in the range 0 to 'i' - 1.

                */

                for (int l = 0; l < i; l++)

                {

                    dp[i][j] = Math.max(dp[i][j], Math.min(dp[l][j - 1], prefixSum[i + 1] - prefixSum[l + 1]));

                }

            }

        }

    

        /*

            'DP[N-1][K]' stores the answer for dividing the array into 'K' parts

            So, return it as the final answer.

        */

        return dp[n - 1][k];

    }

}

Python (3.5)

'''
    Time Complexity: O((N^2)*K)
    Space Complexity: O(N*K)

    Where 'K' denotes the number of friends and 'N' is the number of chunks.
'''

def getMaximumSweetness(arr, k):

    n = len(arr)

    # Base Condition.
    if (k >= n):
        return 0

    # As the number of division is 1 + 'K'.
    k += 1

    # Making the prefix array to store the sum of individual sub arrays.
    prefixSum = [0 for j in range(n + 1)]

    for i in range(n):
        prefixSum[i + 1] = prefixSum[i] + arr[i]

    '''
        Matrix to store the sweetness of the part whose sum of sweetness 
        is minimum after dividing the subarray from indices 0 to 'i' into 'j' parts.
    '''
    dp = [[-float('inf') for j in range(k + 1)] for j in range(n)]

    for i in range(n):
        dp[i][1] = prefixSum[i + 1]

    for i in range(1, n):
        for j in range(2, min(k, i + 1) + 1):
            '''
                Breaking the subarray from indices 0 to 'l' into 'j' - 1 parts
                And then 'l' + 1 to 'i' into 1 part for all 'l' in the range 0 to 'i' - 1.
            '''
            for l in range(i):
                dp[i][j] = max(dp[i][j], min(dp[l][j - 1], prefixSum[i + 1] - prefixSum[l + 1]))

    '''
        'DP[N-1][K]' stores the answer for dividing the array into 'K' parts
        So, return it as the final answer.
    '''
    return dp[n - 1][k]

C++ (g++ 5.4)

/*

	Time Complexity: O((N^2)*K)

    Space Complexity: O(N*K)



    Where 'K' denotes the number of friends and 'N' is the number of chunks.



*/



#include 



int getMaximumSweetness(vector &arr, int k)

{

	int n = arr.size();



	// Base Condition.

	if (k >= n)

	{

		return 0;

	}



	// As the number of division is 1 + 'K'.

	k++;



	// Making the prefix array to store the sum of individual sub arrays.

	vector prefixSum(n + 1, 0);



	for (int i = 0; i < n; i++)

	{

		prefixSum[i + 1] = prefixSum[i] + arr[i];

	}



	/*

        Matrix to store the sweetness of the part whose sum of sweetness 

        is minimum after dividing the subarray from indices 0 to 'i' into 'j' parts.

    */

	vector> dp(n, vector(k + 1, INT_MIN));



	for (int i = 0; i < n; i++)

	{

		dp[i][1] = prefixSum[i + 1];

	}



	for (int i = 1; i < n; i++)

	{

		for (int j = 2; j <= min(k, i + 1); j++)

		{

			/*

                Breaking the subarray from indices 0 to 'l' into 'j' - 1 parts

                And then 'l' + 1 to 'i' into 1 part for all 'l' in the range 0 to 'i' - 1.

            */

			for (int l = 0; l < i; l++)

			{

				dp[i][j] = max(dp[i][j], min(dp[l][j - 1], prefixSum[i + 1] - prefixSum[l + 1]));

			}

		}

	}



    /*

        'DP[N-1][K]' stores the answer for dividing the array into 'K' parts

    	So, return it as the final answer.

    */

	return dp[n - 1][k];

}

Accepted Answer

Binary Search

The idea is to find the range in which the minimum sweetness can lie and then iterate in the given range and find the maximum sweetness you can have. The minimum value possible of sweetness is the minimum sweetness in the given array ‘ARR’, and the maximum value of sweetness is the sum of the sweetness of the chunks in the array ‘ARR’. The goal is to maximize the minimum sweetness one can have. Then use binary search to maximize the minimum sweetness of the divided chunks. The reason is that the range ‘MINSWEETNESS’ to ‘MAXSWEETNESS’ is a sorted range. So, if we can use binary search, then we can cut down the time complexity from O('SUM') to O(log('SUM')) for searching, which increases the efficiency.

There is a base condition: If the number of chunks is less than the number of desired divisions, then Ninja won’t get any chunks. So, the answer will be ‘0’.

The steps are as follows:

Base Condition: If ‘K’ is greater than or equal to the number of chunks in the array ‘ARR’, return ‘0’.
Increment ‘K’ by ‘1’ as there are ‘K’ friends and the number of divisions required is ‘K’ + 1.
Initialize ‘MINSWEETNESS’ = the minimum sweetness in the given array ‘ARR’ and ‘MAXSWEETNESS’ = sum of all the sweetness of the array ‘ARR’.
Execute a while loop with the condition that ‘MAXSHIPCAPACITY’ >= ‘MINSHIPCAPACITY’:
Initialize ‘MIDSWEETNESS’ = ('MINSWEETNESS' + ‘MAXSWEETNESS’)/2.
Check if the given value of ‘MINSWEETNESS’ is taken as the sweetness then Will the distribution be possible?
- Define a function ‘CHECKVALIDITY’ which takes three arguments ‘TARGETSWEETNESS’, ‘NUMS’, and ‘K’, which denotes the sweetness value for which you are checking, the given array ‘NUMS’, and the number of friends you have.
- Initialize two variables, ‘CURRENTFRIENDNUMBER’ equal to '1' and ‘CURRENTSWEETNESS’ to '0', which denotes the current friend number for which we are checking, and the sweetness that the friend has.
- Iterate over the array ‘ARR’:
  - Check if, after adding the current sweetness, the total sweetness for the current friend exceeds the ‘TARGETSWEETNESS’ or not.
  - If it doesn’t exceed, then add the current sweetness to ‘CURRENTSWEETNESS’.
  - If it exceeds, then increase the current friend number and check for the next friend, and then set ‘CURRENTSWEETNESS’ to the value of the current sweetness in the array ‘ARR’.
  - If ‘CURRENTFRIENDNUMBER’ becomes greater than or equal to ‘K’, it means that the division is possible. So, we will return ‘true’.
- Otherwise, we will return 'false'.
- If the function returns ‘true’, then we will update the value of ‘MINSWEETNESS’ to ‘MIDSWEETNESS’. Otherwise, we will update the value of ‘MAXSWEETNESS’ to ‘MAXSWEETNESS’ - 1.
- Now, if the given value of ‘MAXSWEETNESS’ is taken as the sweetness is possible, return ‘MAXSWEETNESS’ as the final answer.
- Otherwise, return ‘MINSWEETNESS’ as the final answer.

Space Complexity: O(1)Explanation:

O(1).

As we are using constant space. Hence, the overall space complexity is O(1).

Time Complexity: OtherExplanation:

O(N * log(SUM)), where ‘SUM’ denotes the sum of the sweetness of all the chunks and ‘N’ is the number of chunks.

We are applying binary search in the range of the maximum value of the array ‘ARR’ and the sum of all values of ‘ARR’. In each iteration, we are iterating over the array ‘ARR’. Hence the overall time complexity is O(N * log(SUM)).