Last Updated: 1 Dec, 2021

Pizza Sharing

Moderate

Asked in companies

Solve now

Problem statement

Ninja and his two friends went to a picnic and enjoy their pizza. But they found that the slices of pizza are not uniform. Ninja is very hungry so he wants to take the bigger slices of pizza. So all friends decided to follow the rule while eating pizza:

1 . Ninja will pick a slice of pizza.
2 . One of his friends will pick the next slice in the anti-clockwise direction.
3 . the Second friend will pick the next slice in the clockwise direction of Ninja’s pick.

You are given an array ‘ARR’ having the weights of ‘N’ slices representing a circular array in the clockwise direction.N is a multiple of 3. Ninja wants to collect the slices such that their sum is maximum. Can you help Ninja to solve this problem and tell him the maximum sum he can achieve?

For Example

If the ARR is [4,3,11,12,2,4] , so the optimal answer will be as follows:
Ninja will pick the slice having weight 12, so his friends will pick the slices having weights 11 and 2. After that Ninja will pick the slice with weight 4 and his friends will pick 4 and 3.
Ninja’s sum will be 16 which is the maximum.

Input Format:

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

The first line of each test case contains a single integer, ‘N’, denoting the number of elements in array ‘ARR’.

The following line contains ‘N’ values corresponding to elements of ‘ARR’.

Output Format:

For each test case, print the maximum sum of the weight of slices.

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

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 1000.
1 <=ARR[i] <=10^6.

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this problem, we can observe a pattern that Ninja can’t take any adjacent slices and the array is a circular array, so if Ninja takes the first slice he can’t take the last slice and vise-versa.

So,we will define a recursive function REC(‘ARR’,N,M) which will return the maximum sum if we choose M slices from first N slices of ‘ARR’.

The value of REC(‘ARR’,N,M) will be maximum of REC(‘ARR’,N-1,M) {Not taking the Nth slice} and ARR[N-1] + REC(‘ARR’,N-2,M-1) {Taking the Nth slice.}

But as we can’t first and last element together,we will create two arrays ARR1(from index 0 to N-2) and ‘ARR2’(from index 1 to index N-1.)

We will run the REC() function for both the array and return the maximum.

Algorithm:

Defining REC(’ARR’,’N’,’M’) function:
- If ‘N’ is less than or equal to 0,no element in the array.
  - Return 0.
- If ‘M’ is equal to 0,all slices are taken.
  - Return 0.
- Return maximum of REC(ARR,N-1,M) and (REC(ARR,N-2,M-1) + ARR[N-1]).
Set ‘ANS’ as 0.
Declare two arrays ‘ARR1’ and ‘ARR2’.
Copy ARR[0..(N-2)] to ‘ARR1’.
Copy ARR[1..(N-1)] to ‘ARR2’.
Set M as N/3 as Ninja can take utmost N/3 slices.
Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR1’,N-1,M).
Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR2’,N-1,M).
Return ‘ANS’.

Solve now

02 Approach

In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each state will be calculated only once.

We will define a 2D array ‘DP’ to store the answers.

Algorithm:

Defining REC(’ARR’,’N’,’M’,DP) function:
- If ‘N’ is less than or equal to 0,no element in the array.
  - Return 0.
- If ‘M’ is equal to 0,all slices are taken.
  - Return 0.
- If DP[N][M] is not equal to -1:
  - Precomputed value found.
  - Return DP[N][M].
- Set DP[N][M] as maximum of REC(ARR,N-1,M) and (REC(ARR,N-2,M-1) + ARR[N-1]).
- Return DP[N][M].
Set ‘ANS’ as 0.
Declare two arrays ‘ARR1’ and ‘ARR2’.
Copy ARR[0..(N-2)] to ‘ARR1’.
Copy ARR[1..(N-1)] to ‘ARR2’.
Set M as N/3 as Ninja can take utmost N/3 slices.
Declare a 2D array ‘DP’ of size (N+1)*(M+1) to memoize the solution.
Set all values of DP to -1.
Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR1’,N-1,M).
Set all values of DP to -1.
Set ‘ANS’ as maximum of ‘ANS’ and REC(‘ARR2’,N-1,M).
Return ‘ANS’.

Solve now

03 Approach

In this approach, we will use dynamic programming and find the answer to the problem. We will prepare 2D array ‘DP’.

DP[i][j] will return the maximum sum if we pick only j slices from the first i slices of the list.

DP[i][j] can be computed as maximum of ( DP[i-1][j] and DP[i-2][j-1] + ARR[i-1]).

So,we iterate over all pairs of i and j and compute the values of DP table for ‘ARR1’ and ‘ARR2’ both and the compare their DP[N-1][M] and return the maximum among them.

Algorithm:

Set ‘ANS’ as 0.
Declare two arrays ‘ARR1’ and ‘ARR2’.
Copy ARR[0..(N-2)] to ‘ARR1’.
Copy ARR[1..(N-1)] to ‘ARR2’.
Set M as N/3 as Ninja can take utmost N/3 slices.
Declare a 2D array ‘DP’ of size (N+1)*(M+1) to memoize the solution.
For i in range 0 to N-1:
- For j in range 0 to M:
  - If i==0 or j==0:
    - Set DP[i][j] as 0.
  - If i==1:
    - Only one element left.
    - Set DP[i][j] as ARR[0].
  - Set DP[i][j] as maximum of DP[i-1][j] and (DP[i-2][j-1] + ARR1[i-1]).
Set ‘ANS’ as maximum of ANS and DP[N-1][M].
Now,find the values of ‘DP’ table corresponding to ‘ARR2’.
For i in range 0 to N-1:
- For j in range 0 to M:
  - If i==0 or j==0:
    - Set DP[i][j] as 0.
  - If i==1:
    - Only one element left.
    - Set DP[i][j] as ARR[0].
  - Set DP[i][j] as maximum of DP[i-1][j] and (DP[i-2][j-1] + ARR2[i-1]).
Set ‘ANS’ as maximum of ANS and DP[N-1][M].
Return ‘ANS’.

Solve now