There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:
You will pick any pizza slice.
Your friend Alice will pick the next slice in the anti-clockwise direction of your pick.
Your friend Bob will pick the next slice in the clockwise direction of your pick.
Repeat until there are no more slices of pizzas.
Given an integer array slices that represent the sizes of the pizza slices in a clockwise direction, return the maximum possible sum of slice sizes that you can pick.
Input: slices =[1,2,3,4,5,6]Output: 10Explanation: Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively. Then Pick slices with size 6,finally Alice and Bob will pick slice of size 2 and 1 respectively. Total =4+6.
Input: slices =[8,9,8,6,1,1]Output: 16Explanation: Pick pizza slice of size 8in each turn. If you pick slice with size 9 your partners will pick slices of size 8.
Since the pizza is circular and you must pick n slices out of 3n, with no two picked slices adjacent, this is a variation of the “House Robber II” problem. We use dynamic programming to maximize the sum, considering two cases: exclude the first slice or exclude the last slice, to avoid picking both ends.
classSolution {
publicintmaxSizeSlices(int[] slices) {
int n = slices.length/ 3;
return Math.max(dp(slices, 0, slices.length-2, n), dp(slices, 1, slices.length-1, n));
}
intdp(int[] arr, int l, int r, int k) {
int m = r-l+1;
int[][] f =newint[m+1][k+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= k; j++) {
f[i][j]= Math.max(f[i-1][j], f[Math.max(0,i-2)][j-1]+arr[l+i-1]);
}
}
return f[m][k];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funmaxSizeSlices(slices: IntArray): Int {
val n = slices.size / 3fundp(arr: IntArray): Int {
val m = arr.size
val f = Array(m+1) { IntArray(n+1) }
for (i in1..m) {
for (k in1..n) {
f[i][k] = maxOf(f[i-1][k], f[maxOf(0,i-2)][k-1]+arr[i-1])
}
}
return f[m][n]
}
val a = slices.sliceArray(0 until slices.size-1)
val b = slices.sliceArray(1 until slices.size)
return maxOf(dp(a), dp(b))
}
}
1
2
3
4
5
6
7
8
9
10
defmaxSizeSlices(slices: list[int]) -> int:
defdp(arr: list[int], k: int) -> int:
m = len(arr)
f = [[0]*(k+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, k+1):
f[i][j] = max(f[i-1][j], f[max(0,i-2)][j-1]+arr[i-1])
return f[m][k]
n = len(slices)//3return max(dp(slices[:-1], n), dp(slices[1:], n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfnmax_size_slices(slices: Vec<i32>) -> i32 {
fndp(arr: &[i32], k: usize) -> i32 {
let m = arr.len();
letmut f =vec![vec![0; k+1]; m+1];
for i in1..=m {
for j in1..=k {
f[i][j] = f[i-1][j].max(f[i.saturating_sub(2)][j-1]+arr[i-1]);
}
}
f[m][k]
}
let n = slices.len()/3;
dp(&slices[..slices.len()-1], n).max(dp(&slices[1..], n))
}
}