<p>There is a pizza with <code>3n</code> slices of varying size, you and your friends will take slices of pizza as follows:</p>

<ul>
	<li>You will pick <strong>any</strong> pizza slice.</li>
	<li>Your friend Alice will pick the next slice in the anti-clockwise direction of your pick.</li>
	<li>Your friend Bob will pick the next slice in the clockwise direction of your pick.</li>
	<li>Repeat until there are no more slices of pizzas.</li>
</ul>

<p>Given an integer array <code>slices</code> that represent the sizes of the pizza slices in a clockwise direction, return <em>the maximum possible sum of slice sizes that you can pick</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/18/sample_3_1723.png" style="width: 500px; height: 266px;" />
<pre>
<strong>Input:</strong> slices = [1,2,3,4,5,6]
<strong>Output:</strong> 10
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/18/sample_4_1723.png" style="width: 500px; height: 299px;" />
<pre>
<strong>Input:</strong> slices = [8,9,8,6,1,1]
<strong>Output:</strong> 16
<strong>Explanation:</strong> Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 * n == slices.length</code></li>
	<li><code>1 &lt;= slices.length &lt;= 500</code></li>
	<li><code>1 &lt;= slices[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def __init__(self):
        self.num_picks = 0  # Number of slices to pick

    def maxSizeSlices(self, slices):
        self.num_picks = len(slices) // 3  # Calculate the number of slices we can pick
        
        # Create an array to store slices without the first element
        slices_excluding_first = slices[1:]
        max_sum_without_first = self._compute_max_sum(slices_excluding_first)
        
        # Create another array to store slices without the last element
        slices_excluding_last = slices[:-1]
        max_sum_without_last = self._compute_max_sum(slices_excluding_last)
        
        # Return the maximum sum of two cases (excluding the first slice or the last slice)
        return max(max_sum_without_first, max_sum_without_last)

    def _compute_max_sum(self, array):
        array_length = len(array)
        # `dp_table` where `dp_table[i][j]` represents the max sum using first `i` elements and `j` picks
        dp_table = [[0] * (self.num_picks + 1) for _ in range(array_length + 1)]
        
        for index in range(1, array_length + 1):
            for picks in range(1, self.num_picks + 1):
                # Choose the larger value between not taking or taking the current element
                dp_table[index][picks] = max(
                    dp_table[index - 1][picks],
                    (dp_table[index - 2][picks - 1] if index >= 2 else 0) + array[index - 1]
                )
        
        # Return the maximum sum for `array_length` elements and `num_picks` picks
        return dp_table[array_length][self.num_picks]

17900