#1388

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Pizza With 3n Slices

Maximize your pizza slice sum from a 3n-sized circular array using state transition dynamic programming efficiently.

array dynamic programming greedy heap priority queue

Problem Statement

You have a pizza divided into 3n slices of varying sizes arranged in a circle. You and two friends will take turns picking slices such that each time you pick one slice, your two friends will take adjacent slices clockwise and counterclockwise, effectively removing three consecutive slices from the circle. Your goal is to maximize the sum of the slices you pick while following this rule.

Given an integer array slices representing the sizes of the pizza slices in clockwise order, return the maximum sum you can achieve by picking exactly n slices from the 3n slices. Each pick removes adjacent slices from the circle, so you must carefully plan your selections to maximize total size. Constraints include 3 * n == slices.length, 1 <= slices.length <= 500, and 1 <= slices[i] <= 1000.

Examples

Example 1

Input: slices = [1,2,3,4,5,6]

Output: 10

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.

Example 2

Input: slices = [8,9,8,6,1,1]

Output: 16

Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.

Constraints

3 * n == slices.length
1 <= slices.length <= 500
1 <= slices[i] <= 1000

Solution Approach

Transform Circular Array to Linear Cases

Split the problem into two linear dynamic programming cases: one excluding the first slice and one excluding the last slice. This converts the circular constraint into manageable linear subproblems, allowing standard DP techniques to compute maximum sums without overlapping conflicts.

Define State Transition

Use a DP table dp[i][k] representing the maximum sum using slices from index i to the end while picking k slices. Transition is dp[i][k] = max(dp[i+1][k], slices[i] + dp[i+2][k-1]). This state captures whether to take the current slice or skip it, reflecting the effect of removing adjacent slices.

Compute and Combine Results

Compute the DP for both linear cases and return the maximum result. This approach ensures all combinations respecting the circular removal rule are considered. Time complexity is O(n^2) and space can be optimized using rolling arrays for dp table.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to iterating over slices and possible picks in DP. Space complexity is O(n^2) for the DP table, reducible to O(n) using optimized rolling array techniques.

What Interviewers Usually Probe

Checking if you recognize the circular array pattern.
Expecting you to translate circular dependency into two linear DP scenarios.
Observing understanding of state transitions for dynamic programming.

Common Pitfalls or Variants

Common pitfalls

Attempting a purely greedy solution without considering adjacent slice removal.
Ignoring the circular array edge cases when picking the first or last slice.
Incorrect DP indexing that does not account for skipping one slice after picking.

Follow-up variants

Select maximum sum from a linear array where picking one element removes its neighbors.
Maximizing non-adjacent selections from a 2n-length array with fixed number of picks.
Generalized k-consecutive removal problem in a circular array.

FAQ

What is the main pattern behind Pizza With 3n Slices?

It follows a state transition dynamic programming pattern where each pick removes adjacent elements, forcing careful selection.

Can a greedy approach solve this problem?

No, greedy choices often fail because selecting the largest available slice can block future optimal picks due to adjacent removal.

How do I handle the circular array edge case?

Split into two linear cases: one excluding the first slice, one excluding the last slice, and take the maximum result from both.

What is the optimal DP state definition?

Use dp[i][k] = max sum obtainable from index i to end when picking k slices, considering skips for adjacent removals.

Can space complexity be optimized?

Yes, the DP table can be reduced from O(n^2) to O(n) by using rolling arrays for previous and current states.

terminal

Solution

Solution 1: Dynamic Programming

We can transform this problem into: In a circular array of length $3n$, select $n$ non-adjacent numbers so that the sum of these $n$ numbers is maximized.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        def g(nums: List[int]) -> int:
            m = len(nums)
            f = [[0] * (n + 1) for _ in range(m + 1)]
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    f[i][j] = max(
                        f[i - 1][j], (f[i - 2][j - 1] if i >= 2 else 0) + nums[i - 1]
                    )
            return f[m][n]

        n = len(slices) // 3
        a, b = g(slices[:-1]), g(slices[1:])
        return max(a, b)

Continue Practicing

#871 minimum number of refueling stops #1383 maximum performance of a team #1402 reducing dishes