<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 {
    // ismein adjacent nikal ne ki zarrorat hi nahi bas stoper use karna
    int solve(vector<int>s,int i,vector<int>&dp){
        if(i>=s.size()){
            return 0;
        }
        if(s[i]==-1){
            return 0;
        }
        
        
        int take=s[i];
        bool f=0;
        int a,b;
        for(int j=i-1;j>=0;j--){
            if(s[j]!=-1){
                f=1;
                a=j;
                break;
            }
        }
        if(!f){
            for(int j=s.size()-1;j>i;j--){
                if(s[j]!=-1){
                    f=1;
                    a=j;
                    break;
                }   
            }
        }
        bool f1=0;
        for(int j=i+1;j<s.size();j++){
            if(s[j]!=-1){
                f1=1;
                b=j;
                break;
            }
        }
        if(!f1){
            for(int j=0;j<i;j++){
                if(s[j]!=-1){
                    f1=1;
                    b=j;
                    break;
                }   
            }
        }
        // if(i==3){
        //     cout<<f<<" "<<f1<<endl;
        //     cout<<a+1<<" "<<b+1<<endl;

        // }
            
        // if(f && f1 && dp[i]!=-1){
        //     return dp[i];
        // }
        int ele=s[i];
        int ex=solve(s,i+1,dp);
        s[a]=-1;
        s[b]=-1;
        s[i]=-1;
        take+=solve(s,i+2,dp);
        
        // cout<<ele<<" "<<take<<" "<<ex<<endl;
        return dp[i]=max(take,ex);
        

    }
    int solve2(vector<int>&s,int i,int endi,int n,vector<vector<int>>&dp){
        if(n==0 || i>=endi){
            return 0;
        }
        if(dp[i][n]!=-1){
            return dp[i][n];
        }
        int in=s[i]+solve2(s,i+2,endi,n-1,dp);
        int ex=solve2(s,i+1,endi,n,dp);
        // cout<<i<<" "<<n<<endl;
        // cout<<
    
        return dp[i][n]=max(in,ex);
    }
    int solveTab(vector<int>&s,int start,int end){
        int n=s.size();
        vector<vector<int>>dp(n+1,vector<int>(n/3+1,0));
        for(int i=end-1;i>=start;i--){
            for(int k=n/3;k>0;k--){
                int a=s[i];
                if(i+2<end){
                    a+=dp[i+2][k-1];
                }
                int b=dp[i+1][k];
                dp[i][k]=max(a,b);
            }
        }
        return dp[start][n/3];
    }
    int solveTab2(vector<int>&s,int start,int end){
        int n=s.size();
        // vector<vector<int>>dp(n+1,vector<int>(n/3+1,0));
        vector<int>curr(n/3+1,0);
        vector<int>next(n/3+1,0);
        for(int i=end-1;i>=start;i--){
            vector<int> prev(n/3+1,0);
            for(int k=n/3;k>0;k--){
                int a=s[i];
                if(i+2<end){
                    a+=next[k-1];
                }
                int b=curr[k];
                prev[k]=max(a,b);
            }
            next=curr;
            curr=prev;
        }
        return curr[n/3];
    }
    
public:
    int maxSizeSlices(vector<int>& s) {
        // vector<int>dp(s.size()+1,-1);
        // int ans=solve(s,0,dp); wrong one
        int n=s.size();
        // vector<vector<int>>dp(n,vector<int>(n/3+1,-1));
        // int a=solve2(s,0,n-1,n/3,dp);
        // vector<vector<int>>dp1(n,vector<int>(n/3+1,-1));
        // int b=solve2(s,1,n,n/3,dp1);
        // cout<<a<<" "<<b<<endl;
        int a=solveTab2(s,0,n-1);
        int b=solveTab2(s,1,n);

        int ans=max(a,b);
        return ans;
        
    }
};
16200