Skip to content

1388. Pizza With 3n Slices 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def maxSizeSlices(self, slices: list[int]) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      """
      Returns the maximum the sum of slices if you can pick k slices from
      slices[i..j).
      """
      if k == 1:
        return max(slices[i:j])
      # Note that j - i is not the number of all the left slices. Since you
      # Might have chosen not to take a slice in a previous step, there would be
      # Leftovers outside [i:j]. If you take slices[i], one of the slices your
      # Friends take will be outside of [i:j], so the length of [i:j] is reduced
      # By 2 instead of 3. Therefore, the minimum # Is 2 * k - 1 (the last step only
      # Requires one slice).
      if j - i < 2 * k - 1:
        return -math.inf
      return max(slices[i] + dp(i + 2, j, k - 1),
                 dp(i + 1, j, k))

    k = len(slices) // 3
    return max(dp(0, len(slices) - 1, k),
               dp(1, len(slices), k))