Problem statement

https://leetcode.com/problems/pizza-with-3n-slices/

Solution

It can be shown that problem is equivalent to choosing n elements out of 3n, such we did not choose any adjacent elements. It can be done in O(n^2) time complexity using dp with state dp(i, j), where i is index we reached so far and j is number of pieces we taken.

Proof by induction. For n = 1, result is obvious. For general n it is enough to show that we can remove one slice without creating any adjacent slices among remaining chosen n-1 slices. It is true, because average size of gap equal 2 and by pigeonhole principle there is gap with size >=2. We remove a chosen slice next to this gap. One of the gap slices will be removed, eaving at least one remaining, therefore ensuring that te two chosen pieces nearest to the removed slice do not end up adjacent. QED.

Complexity

Time and space complexity is O(n^2)

Code

class Solution:
    def maxSizeSlices(self, S):
        def solve(A, take):
            @lru_cache(None)
            def dp(i, j):
                if i < 0: return -abs(j)*10**9
                return max(dp(i - 2, j - 1) + A[i], dp(i - 1, j))
            return dp(len(A) - 1, take)
        
        return max(solve(S[:-1], len(S)//3), solve(S[1:], len(S)//3))