Pizza with 3n slices

Array Dynamic Programming Greedy Heap (Priority Queue)

53.8% acceptance

Feb 25, 2026

1134

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_size_slices(slices: Vec<i32>) -> i32 {
    // Pick n/3 non-adjacent elements from circular array of 3n
    // Reduces to: max sum of n/3 non-adjacent from linear array excluding either first or last
    let n = slices.len();
    let k = n / 3;
    fn max_non_adj(arr: &[i32], pick: usize) -> i32 {
      let m = arr.len();
      // dp[i][j] = max sum picking j elements from first i elements
      let mut dp = vec![vec![0i32; pick + 1]; m + 1];
      for i in 1..=m {
        for j in 1..=pick.min(i) {
          dp[i][j] = dp[i-1][j]; // skip arr[i-1]
          if i >= 2 {
            dp[i][j] = dp[i][j].max(dp[i-2][j-1] + arr[i-1]);
          } else {
            dp[i][j] = dp[i][j].max(arr[i-1]);
          }
        }
      }
      dp[m][pick]
    }
    max_non_adj(&slices[..n-1], k).max(max_non_adj(&slices[1..], k))
  }
}