// 演算法：與 C 版相同的區間 DP。dp[i][j] = 面對 [i..j] 的玩家淨領先分差。
// Algorithm: same interval DP as the C version. dp[i][j] = net lead of the player facing [i..j].
// 轉移取「拿左」「拿右」兩選擇的較大值；dp[0][n-1] > 0 即 Alice 贏。
// Transition = max(take-left, take-right); dp[0][n-1] > 0 means Alice wins.

#include <vector>      // 提供 std::vector，會自動管理記憶體 / gives std::vector, which frees itself
#include <algorithm>   // 提供 std::max / gives std::max

using namespace std;

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();                        // n 是堆數 / number of piles

        // vector<vector<int>> 是「向量的向量」，即自動管理的二維陣列，全部初始化為 0。
        // vector<vector<int>> is a vector of vectors — a self-managing 2D array, all zeros.
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // 基底：單堆時淨領先等於該堆石子數 / base case: single pile -> lead equals its stones.
        for (int i = 0; i < n; i++)
            dp[i][i] = piles[i];

        // 依區間長度由小到大填表 / fill by increasing interval length.
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;                 // 右端索引 / right-end index

                int takeLeft  = piles[i] - dp[i + 1][j];  // 拿左端 / take the left pile
                int takeRight = piles[j] - dp[i][j - 1];  // 拿右端 / take the right pile

                // std::max 回傳兩者較大者，代表最佳選擇 / std::max keeps the better option.
                dp[i][j] = max(takeLeft, takeRight);
            }
        }

        // dp[0][n-1] > 0 表示先手 Alice 最終淨領先 / positive net lead for the first mover.
        return dp[0][n - 1] > 0;
    }
};