public class Solution {
    public bool PredictTheWinner(int[] nums) {
        //    int n = nums.Length;
            //    int[,] dp = new int[n, n];
            //    for (int i = 0; i < n; i++) { dp[i, i] = nums[i]; }
            //    for (int len = 1; len < n; len++)
            //    {
            //        for (int i = 0; i < n - len; i++)
            //        {
            //            int j = i + len;
            //            dp[i, j] = Math.Max(nums[i] - dp[i + 1, j], nums[j] - dp[i, j - 1]);
            //        }
            //    }
            //    return dp[0, n - 1] >= 0;

            if (nums == null) { return true; }
            int n = nums.Length;
            if ((n & 1) == 0) { return true; } // Improved with hot13399‘s comment.
            int[] dp = new int[n];
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = i; j < n; j++)
                {
                    if (i == j)
                    {
                        dp[i] = nums[i];
                    }
                    else
                    {
                        dp[j] = Math.Max(nums[i] - dp[j], nums[j] - dp[j - 1]);
                    }
                }
            }
            return dp[n - 1] >= 0;
    }
}