Maximum Pizza Slices

Problem Understanding

We are given a circular array slices of size 3n, representing the sizes of pizza slices. We need to pick n slices such that no two adjacent slices are picked. Our goal is to maximize the total size of the slices we pick.

Naive Approach (Brute Force)

A brute-force approach would involve trying all possible combinations of picking n slices such that no two picked slices are adjacent. This is computationally expensive and impractical for larger inputs. We would generate all possible subsets of size n and check each subset if there are adjacent elements. If not, we'd add the values to that subset and save the maximum sum among all these subsets.

Time Complexity: O(C(3n, n)), where C is the binomial coefficient. This is because we'd have to try out every possible n-sized subset of the 3n slices.

Space Complexity: O(n), to store each possible subset.

Optimal Approach (Dynamic Programming)

The problem can be efficiently solved using dynamic programming. Since the pizza is circular, we can break it down into two linear subproblems:

1. Consider the slices from index 0 to 3n - 2. Find the maximum sum of n non-adjacent slices.
2. Consider the slices from index 1 to 3n - 1. Find the maximum sum of n non-adjacent slices.

The overall answer is the maximum of these two results.

For each linear subproblem, we can use a 2D DP array dp[i][j] where:

• i represents the number of slices considered so far (from 0 to 3n - 2 or 1 to 3n - 1).
• j represents the number of slices we have picked so far (from 0 to n).

dp[i][j] stores the maximum sum achievable by picking j slices from the first i slices.

The DP relation is as follows:

dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + slices[i-1])

• dp[i-1][j] means we don't pick the i-th slice.
• dp[i-2][j-1] + slices[i-1] means we pick the i-th slice, so we can't pick the adjacent i-1 slice.

Base Cases:

• dp[i][0] = 0 for all i (picking 0 slices results in a sum of 0).
• dp[0][0] = 0

Algorithm:

1. Define a function solve(slices, n) that takes a linear slice array and the number of slices to pick as input and returns the maximum sum using dynamic programming as described above.
2. Call solve twice:
   • Once with slices[0...3n-2] and n.
   • Once with slices[1...3n-1] and n.
3. Return the maximum of the two results.

Edge Cases

• If n is 1, simply return the maximum value in the slices array.
• If the input slices array is empty, return 0.

Code Example (Python)

def solve(slices, n):
    k = len(slices)
    dp = [[0] * (n + 1) for _ in range(k + 1)]

    for i in range(1, k + 1):
        for j in range(1, n + 1):
            dp[i][j] = max(dp[i-1][j], (dp[i-2][j-1] + slices[i-1]) if i > 1 else slices[i-1])

    return dp[k][n]

def maxSizeSlices(slices):
    n = len(slices) // 3
    if n == 1:
        return max(slices)
    
    return max(solve(slices[:-1], n), solve(slices[1:], n))

Time and Space Complexity

Time Complexity: O(n*n), where n is the length of the input slices array divided by 3. This is because the solve function iterates through the dp array of size k * n, where k is approximately 2n

Space Complexity: O(n*n), to store the dp array.