class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int length = nums.size();
        std::vector< std::vector<int> > s(length, std::vector<int> (length));
        for(int l = 0; l < length; l++){
            for(int i=0; i < length - l; i++){
                if(l==0) s[i][l] = nums[i];
                else if (l==1) s[i][l] = max(nums[i], nums[i+1]);
                else if (l==2) s[i][l] = max(nums[i] + min(nums[i+1], nums[i+2]),
                                             nums[i+2] + min(nums[i], nums[i+1]));
                else s[i][l] = max(nums[i] + min(s[i+2][l-2], s[i+1][l-2]),
                                   nums[i+l] + min(s[i][l-2], s[i+1][l-2]));
            }
        }
        int t = 0;
        for(const auto & it : nums)
            t += it;
        return (s[0][length-1] >= t-s[0][length-1]);
    }
};