# Pizza With 3n Slices
**Difficulty:** HARD
[External](https://leetcode.com/problems/pizza-with-3n-slices)
Canonical: https://scaleengineer.com/dsa/problems/pizza-with-3n-slices
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/pizza-with-3n-slices/image0.png) 

**Input:** slices = [1,2,3,4,5,6]
**Output:** 10
**Explanation:** 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:**

![](https://assets.glich.co/dsa/pizza-with-3n-slices/image1.png) 

**Input:** slices = [8,9,8,6,1,1]
**Output:** 16
**Explanation:** 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`

# Approaches
## Dynamic Programming
The problem can be rephrased as "select `n` non-adjacent slices from a circular array of `3n` slices to maximize the sum". The circular nature means the first and last slices are adjacent and cannot be picked together. This constraint can be handled by breaking the problem into two independent subproblems for a linear array:
1. Maximum sum from slices `0` to `3n-2`.
2. Maximum sum from slices `1` to `3n-1`.
The final answer is the maximum of the solutions to these two subproblems. Each subproblem, which is to find the maximum sum of `n` non-adjacent items in a linear array, can be solved using dynamic programming.
**Time:** O(m * n) or O(m^2) since `n = m/3`. We run the `solve` function twice, and each call involves nested loops of size `m-1` and `n`. · **Space:** O(m * n) or O(m^2). The space is dominated by the 2D DP table of size `(m-1+1) x (n+1)`.
**Pros:** It's a standard and clear dynamic programming solution that correctly solves the problem.; The logic is a direct translation of the recurrence relation.
**Cons:** The space complexity is `O(m*n)`, which can be large for the given constraints, although it fits within typical memory limits.
### Explanation
Let's define a function `solve(arr)` that finds the maximum sum of `n` non-adjacent elements in a linear array `arr`.
We use a 2D DP table, `dp[i][j]`, to store the maximum sum we can obtain by choosing `j` slices from the first `i` slices of the input array `arr`.
The state transition is as follows:
For each slice `arr[i-1]` (using 1-based indexing for `i`), we have two choices:
1.  **Don't pick `arr[i-1]`**: The maximum sum is the same as what we could get from the first `i-1` slices by picking `j` slices. This value is `dp[i-1][j]`.
2.  **Pick `arr[i-1]`**: If we pick `arr[i-1]`, we cannot pick its neighbor `arr[i-2]`. So, we must have picked `j-1` slices from the first `i-2` slices. The sum would be `arr[i-1] + dp[i-2][j-1]`.
The recurrence relation is: `dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1])`.
The base cases are `dp[0][j] = 0` and `dp[i][0] = 0`. The final result for a subproblem of length `L` is `dp[L][n]`.
```java
public class Solution {
    public int maxSizeSlices(int[] slices) {
        int m = slices.length;
        int n = m / 3;
        
        // Case 1: Exclude the last slice
        int[] slices1 = new int[m - 1];
        System.arraycopy(slices, 0, slices1, 0, m - 1);
        int ans1 = solve(slices1, n);
        
        // Case 2: Exclude the first slice
        int[] slices2 = new int[m - 1];
        System.arraycopy(slices, 1, slices2, 0, m - 1);
        int ans2 = solve(slices2, n);
        
        return Math.max(ans1, ans2);
    }
    
    private int solve(int[] arr, int k) {
        int len = arr.length;
        int[][] dp = new int[len + 1][k + 1];
        
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= k; j++) {
                int notPick = dp[i - 1][j];
                int pick = (i >= 2 ? dp[i - 2][j - 1] : 0) + arr[i - 1];
                // It's impossible to pick j items from less than 2j-1 items.
                // This is implicitly handled if we consider that dp[i-2][j-1] would be 0
                // if it was impossible to form that sum.
                // A more robust way is to check explicitly.
                if (2 * j > i + 1) { // or 2*j-1 > i
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(pick, notPick);
                }
            }
        }
        
        return dp[len][k];
    }
}
```
### Algorithm
*   Let `m` be the total number of slices and `n = m / 3`.
*   To handle the circular dependency, we solve two separate problems on linear arrays:
    1.  Find the max sum for `slices[0...m-2]`.
    2.  Find the max sum for `slices[1...m-1]`.
*   The overall answer is the maximum of the results of these two subproblems.
*   For each subproblem, we use a helper function `solve(arr, k)` which calculates the maximum sum of `k` non-adjacent elements from a linear array `arr`.
*   Inside `solve`, we use a 2D DP array `dp[i][j]` representing the max sum from the first `i` elements by picking `j` of them.
*   The DP table is filled using the recurrence: `dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1])`.
*   The result for a subproblem is `dp[arr.length][k]`.

## Space-Optimized Dynamic Programming
This approach builds upon the previous DP solution by optimizing its space complexity. In the recurrence `dp[i][j] = max(dp[i-1][j], arr[i-1] + dp[i-2][j-1])`, we can observe that the computation for the current row `i` only depends on the two preceding rows, `i-1` and `i-2`. This allows us to avoid storing the entire 2D DP table and instead only keep track of the last two rows.
**Time:** O(m * n) or O(m^2). The number of computations is the same as the unoptimized version. · **Space:** O(n) or O(m). We only need to store a few arrays of size `n+1` to compute the result.
**Pros:** Highly efficient in terms of space, reducing it from quadratic to linear.; Maintains the same time efficiency as the unoptimized DP approach.
**Cons:** The implementation can be slightly trickier to get right due to managing the rolling arrays.
### Explanation
The core idea remains the same: break the circular array problem into two linear array subproblems. The optimization lies within the `solve` helper function.
Instead of a `(len+1) x (k+1)` DP table, we use three 1D arrays, say `prev2`, `prev1`, and `curr`, each of size `k+1`.
- `prev2` stores the DP values for row `i-2`.
- `prev1` stores the DP values for row `i-1`.
- `curr` is used to compute the DP values for the current row `i`.

The update rule becomes: `curr[j] = max(prev1[j], arr[i-1] + prev2[j-1])`.
After iterating through all `j` for a given `i`, we update the pointers for the next iteration: `prev2` becomes `prev1`, and `prev1` becomes `curr`. This rolling array mechanism reduces the space from `O(m*n)` to `O(n)`.
```java
public class Solution {
    public int maxSizeSlices(int[] slices) {
        int m = slices.length;
        int n = m / 3;
        
        int[] slices1 = new int[m - 1];
        System.arraycopy(slices, 0, slices1, 0, m - 1);
        int ans1 = solve(slices1, n);
        
        int[] slices2 = new int[m - 1];
        System.arraycopy(slices, 1, slices2, 0, m - 1);
        int ans2 = solve(slices2, n);
        
        return Math.max(ans1, ans2);
    }
    
    private int solve(int[] arr, int k) {
        int len = arr.length;
        if (k == 0) {
            return 0;
        }
        
        int[] prev2 = new int[k + 1]; // Corresponds to dp[i-2]
        int[] prev1 = new int[k + 1]; // Corresponds to dp[i-1]
        
        for (int i = 1; i <= len; i++) {
            int[] curr = new int[k + 1]; // Corresponds to dp[i]
            for (int j = 1; j <= k; j++) {
                if (2 * j - 1 > i) {
                    curr[j] = prev1[j];
                } else {
                    int notPick = prev1[j];
                    int pick = arr[i - 1] + prev2[j - 1];
                    curr[j] = Math.max(pick, notPick);
                }
            }
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1[k];
    }
}
```
### Algorithm
*   The overall structure is identical to the first approach: solve two linear subproblems for `slices[0...m-2]` and `slices[1...m-1]`.
*   The `solve(arr, k)` function is optimized for space.
*   Initialize two 1D arrays, `prev2` and `prev1`, of size `k+1` to represent the DP states for rows `i-2` and `i-1`.
*   Iterate `i` from 1 to `arr.length`. In each iteration:
    *   Create a new 1D array `curr` of size `k+1` for the current row `i`.
    *   Iterate `j` from 1 to `k` and compute `curr[j] = max(prev1[j], arr[i-1] + prev2[j-1])`, with a check for feasibility.
    *   After the inner loop, update `prev2 = prev1` and `prev1 = curr`.
*   The result for the subproblem is `prev1[k]`.

# Solutions
### Java

```java
class Solution {
private
  int n;
public
  int maxSizeSlices(int[] slices) {
    n = slices.length / 3;
    int[] nums = new int[slices.length - 1];
    System.arraycopy(slices, 1, nums, 0, nums.length);
    int a = g(nums);
    System.arraycopy(slices, 0, nums, 0, nums.length);
    int b = g(nums);
    return Math.max(a, b);
  }
private
  int g(int[] nums) {
    int m = nums.length;
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        f[i][j] =
            Math.max(f[i - 1][j], (i >= 2 ? f[i - 2][j - 1] : 0) + nums[i - 1]);
      }
    }
    return f[m][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSizeSlices(vector<int> &slices) {
    int n = slices.size() / 3;
    auto g = [&](vector<int> &nums) -> int {
      int m = nums.size();
      int f[m + 1][n + 1];
      memset(f, 0, sizeof f);
      for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
          f[i][j] =
              max(f[i - 1][j], (i >= 2 ? f[i - 2][j - 1] : 0) + nums[i - 1]);
        }
      }
      return f[m][n];
    };
    vector<int> nums(slices.begin(), slices.end() - 1);
    int a = g(nums);
    nums = vector<int>(slices.begin() + 1, slices.end());
    int b = g(nums);
    return max(a, b);
  }
};

```

### Python

```python
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)

```