Pizza With 3n Slices

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.

For example:

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.

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.

def solve():
    def max_slices(slices):
        n = len(slices) // 3

        def calculate_max_sum(arr):
            m = len(arr)
            dp = [[0] * (n + 1) for _ in range(m + 1)]
            
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    dp[i][j] = max(dp[i-1][j], (arr[i-1] + (dp[i-2][j-1] if i > 1 else 0)))
            return dp[m][n]

        # Case 1: First slice is included
        max_sum1 = calculate_max_sum(slices[:-1])
        
        # Case 2: First slice is not included
        max_sum2 = calculate_max_sum(slices[1:])
        
        return max(max_sum1, max_sum2)

    slices1 = [1, 2, 3, 4, 5, 6]
    print(f"Input: {slices1}, Output: {max_slices(slices1)}")

    slices2 = [8, 9, 8, 6, 1, 1]
    print(f"Input: {slices2}, Output: {max_slices(slices2)}")

    slices3 = [4,1,2,5,8,3,1,9,7]
    print(f"Input: {slices3}, Output: {max_slices(slices3)}")


solve()

Explanation:

The problem requires finding the maximum sum of slice sizes you can pick from a pizza divided into 3n slices, given that you, Alice, and Bob take turns picking slices in a specific order.

The approach is to use dynamic programming to solve this optimally. Since the pizza is circular, we consider two cases:

1. The first slice is included in the selection.
2. The first slice is not included in the selection.

For each case, we create a sub-array and apply dynamic programming to find the maximum sum of n slices such that no two adjacent slices are chosen. This is a variation of the house robber problem.

Dynamic Programming:

dp[i][j] represents the maximum sum achievable by picking j slices from the first i slices of the array.

The transition function is:

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

Where:

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

Finally, the maximum of the two cases (including and excluding the first slice) is returned.

Time Complexity Analysis:

The time complexity is dominated by the dynamic programming calculation, which is O(n * m), where m is the length of the slice array, and n is the number of slices we need to pick. In this case, since we iterate over the array with length at most 3n twice, and the inner loop iterates up to n, the time complexity is O(n * (3n)) = O(n^2). Specifically O(n^2).

Space Complexity Analysis:

The space complexity is determined by the DP table, which has dimensions (m+1) x (n+1), where m is the number of slices in the sub-array (either 3n-1 or 3n-1), and n is the number of slices to pick. Thus, the space complexity is O(n^2) since the dimension is proportional to 3n.

Edge Cases:

1. Empty Input: If the input array is empty, return 0.
2. Small Input: If n is 1 or 2, handle them specifically.
3. Negative values: If there are negative slice sizes, the algorithm still works, but it is important to make sure that it handles negative values appropriately during maximization.