<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>

/* 
Bài này khó ở chỗ hướng tư duy.
Có hai luận điểm chính để đi đến lời giải.
Luận điểm 1: Ta có thể quy bài toán về việc tìm ra n số không liền kề nhau có tổng lớn nhất.
Tại sao lại như thế: 
Do là ta hoàn toàn chủ động trong việc chọn ra n số, Alice và Bob chỉ chọn 2 số ngay bên cạnh số
mà ta đã chọn.
Và do là thứ tự chọn không quan trọng nên chỉ cần là n số không liền kề thì ta luôn có cách để chọn vào những số đó.
Luận điểm thứ hai: Do là dãy số thể hiện cho một vòng tròn, số đầu tiên và số cuối sẽ kề nhau.
Để tránh việc bị chọn trùng số đầu và số cuối. 
Ta sẽ tính với 2 dãy số tạo ra từ dãy số gốc (bỏ số đầu tiên, bỏ số cuối).
*/
void printArr(const vector<int> & a){
    for(int i = 0 ; i < a.size() ; i ++) cout<<a[i]<<" ";
    cout<<endl;
}
void printArr(const vector<vector<int>> & a){
    for(int i = 0 ; i < a.size() ; i ++) printArr(a[i]);
    cout<<endl;
}
class Solution {
public:
    int Helper(const vector<int> & a, int n){
        vector<vector<int>> dp(n, vector<int>(a.size(), 0));
        int i, j;
        for(i = 0 ; i < a.size() ; i ++) dp[0][i] = a[i];
        for(i = 1 ; i < dp[0].size() ; i ++) dp[0][i] = max(dp[0][i], dp[0][i - 1]);
        for(i = 1 ; i < dp.size() ; i ++){
            for(j = 0 ; j < dp[0].size() ; j ++){
                if(j - 2 >= 0) dp[i][j] = a[j] + dp[i - 1][j - 2];
            }
            for(j = 1 ; j < dp[i].size() ; j ++) dp[i][j] = max(dp[i][j],  dp[i][j - 1]);
        }
        int ans = 0;
        for(i = 0 ; i < dp[0].size() ; i ++) ans = max(ans, dp.back()[i]);
        //cout<<"dp:"<<endl;
        //printArr(dp);
        return ans;
    }
    int maxSizeSlices(vector<int>& slices) {
        vector<int> a1, a2;
        int i;
        for(i = 0 ; i < slices.size() - 1 ; i ++){
            a1.push_back(slices[i]);
            a2.push_back(slices[i + 1]);
        }
        int ans1 = Helper(a1, slices.size() / 3);
        int ans2 = Helper(a2, slices.size() / 3);
        return max(ans1, ans2);
    }
};
15900