In this guide, you will get 1388. Pizza With 3n Slices LeetCode Solution with the best time and space complexity. The solution to Pizza With n Slices problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Example 1:
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.
Example 2:
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.
1388. Pizza With 3n Slices LeetCode Solution in C++
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)) /* code provided by PROGIEZ */
1388. Pizza With 3n Slices LeetCode Solution in Java
N/A // code provided by PROGIEZ
1388. Pizza With 3n Slices LeetCode Solution in Python
