/*
 * @lc app=leetcode.cn id=486 lang=cpp
 *
 * [486] 预测赢家
 */

// @lc code=start
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > diff(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            diff[i][i] = nums[i];
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                diff[i][j] = max(nums[i] - diff[i + 1][j], nums[j] - diff[i][j - 1]);
            }
        }
        return diff[0][n - 1] >= 0;
    }
};
// @lc code=end