Pizza With 3n Slices

hard dp house robber heap

Problem

There are 3n pizza slices arranged in a circle. You pick a slice; then your friend Alice takes the slice clockwise of yours and Bob the slice anticlockwise. This repeats until none remain, so you end up with exactly n slices, none of them adjacent. Return the maximum total size of the slices you can pick.

Inputslices = [1,2,3,4,5,6]

Output10

n = 6/3 = 2. Pick non-adjacent slices summing to the max: 4 + 6 = 10.

slices (length multiple of 3)

def max_size_slices(slices):
    total = len(slices)
    pick = total // 3

    # Max sum choosing 'pick' non-adjacent items from a linear array a.
    def best(a):
        m = len(a)
        # dp[i][j] = best using first i items choosing j, item i-1 allowed
        dp = [[0] * (pick + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, pick + 1):
                take = (dp[i - 2][j - 1] if i >= 2 else 0) + a[i - 1]
                dp[i][j] = max(dp[i - 1][j], take)
        return dp[m][pick]

    # Circular: slice 0 and slice 3n-1 are adjacent, so drop one end.
    return max(best(slices[1:]), best(slices[:-1]))

function maxSizeSlices(slices) {
  const total = slices.length, pick = total / 3;
  function best(a) {
    const m = a.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(pick + 1).fill(0));
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= pick; j++) {
        const take = (i >= 2 ? dp[i - 2][j - 1] : 0) + a[i - 1];
        dp[i][j] = Math.max(dp[i - 1][j], take);
      }
    }
    return dp[m][pick];
  }
  return Math.max(best(slices.slice(1)), best(slices.slice(0, -1)));
}

class Solution {
    int pick;
    public int maxSizeSlices(int[] slices) {
        int total = slices.length;
        pick = total / 3;
        int[] a = Arrays.copyOfRange(slices, 1, total);
        int[] b = Arrays.copyOfRange(slices, 0, total - 1);
        return Math.max(best(a), best(b));
    }
    int best(int[] a) {
        int m = a.length;
        int[][] dp = new int[m + 1][pick + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= pick; j++) {
                int take = (i >= 2 ? dp[i - 2][j - 1] : 0) + a[i - 1];
                dp[i][j] = Math.max(dp[i - 1][j], take);
            }
        }
        return dp[m][pick];
    }
}

class Solution {
    int pick;
    int best(vector<int>& a) {
        int m = a.size();
        vector<vector<int>> dp(m + 1, vector<int>(pick + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= pick; j++) {
                int take = (i >= 2 ? dp[i - 2][j - 1] : 0) + a[i - 1];
                dp[i][j] = max(dp[i - 1][j], take);
            }
        }
        return dp[m][pick];
    }
public:
    int maxSizeSlices(vector<int>& slices) {
        int total = slices.size();
        pick = total / 3;
        vector<int> a(slices.begin() + 1, slices.end());
        vector<int> b(slices.begin(), slices.end() - 1);
        return max(best(a), best(b));
    }
};

Explanation

Every round you take one slice and the two neighbours vanish to Alice and Bob. After all rounds you hold exactly n = 3n/3 slices, and crucially no two of your slices are adjacent on the original circle. So the task is: from a circle of 3n values pick n non-adjacent ones with maximum sum — a constrained House Robber.

The new twist versus plain House Robber is the fixed count: we must take exactly n. So the DP needs a second dimension. Let dp[i][j] = the best sum using the first i items while choosing exactly j of them, with adjacency forbidden.

For item i we either skip it (dp[i-1][j]) or take it, which forbids item i-1 and uses one pick: dp[i-2][j-1] + a[i-1]. We keep the larger.

The circle is handled the standard way: slice 0 and slice 3n-1 are neighbours, so they can't both be chosen. We run the linear DP twice — once on the array without the first slice, once without the last — and take the better. Each run picks n items from a line, which is safe.

Example: slices = [1,2,3,4,5,6], n = 2. The best non-adjacent pair is 4 + 6 = 10.

Time: O(n²) Space: O(n²)