// 演算法 / Algorithm:
// 與 C 版相同的區間 DP：dp[i][j] = 面對子陣列 nums[i..j] 時，先取者能保證的
// (自己 - 對手) 最大分數差。取左 / 取右擇優，最後看 dp[0][n-1] >= 0。
// Same interval DP as the C version over the score difference.

#include <vector>      // std::vector 動態陣列 / dynamic array container
using namespace std;

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();          // .size() 回傳元素個數 / number of elements

        // vector<vector<int>> 是「二維陣列」；建一個 n x n、初值全 0 的表格
        // A 2D vector (rows of ints); n x n, all initialized to 0
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // Base case：長度為 1 的區間，先取者直接拿走該數
        // Base case: on a single-element subarray, just take that number
        for (int i = 0; i < n; ++i)
            dp[i][i] = nums[i];

        // 由短到長填表；短區間先算好，長區間才能引用它們
        // Build up by length so longer subarrays can reuse shorter results
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;  // 右端點 / right endpoint

                // 取左端：對手在 nums[i+1..j] 的優勢就是我的劣勢
                // Take left: opponent's advantage on nums[i+1..j] counts against me
                int pickLeft  = nums[i] - dp[i + 1][j];

                // 取右端：對手在 nums[i..j-1] 的優勢就是我的劣勢
                // Take right: symmetric
                int pickRight = nums[j] - dp[i][j - 1];

                // std::max 回傳兩者中較大值 / max returns the larger of the two
                dp[i][j] = max(pickLeft, pickRight);
            }
        }

        // 先手在整段陣列上的最佳差值 >= 0 即玩家 1 不會輸
        // Player 1 doesn't lose iff their best whole-array gap is >= 0
        return dp[0][n - 1] >= 0;
    }
};