预测赢家问题（数组可能包含负数） 题目描述： 给定一个整数数组 nums，两个玩家轮流从数组的任意一端取走一个数字，每次只能取最左边或最右边的数字。玩家1先手，玩家2后手。每个玩家都希望自己最终获得的总分数最大化。如果玩家1能获胜（即总得分大于或等于玩家2），返回 true；否则返回 false。数组可能包含负数。 解题过程： 步骤1：问题分析 这是一个典型的零和博弈问题，两个玩家都采取最优策略。由于数组可能包含负数，我们需要考虑所有可能的游戏状态。每个状态可以用区间 [ i, j ] 来表示当前剩余的数字范围。 步骤2：状态定义 定义 dp[ i][ j] 表示当数组剩余部分为 nums[ i..j ] 时，当前玩家（不一定是玩家1）能比对手多得的分数。 具体来说： 如果 dp[ i][ j ] > 0，当前玩家获胜 如果 dp[ i][ j] < 0，当前玩家输给对手 如果 dp[ i][ j ] = 0，平局 步骤3：状态转移 对于区间 [ i, j ]，当前玩家有两种选择： 取走 nums[ i]，那么对手会在区间 [ i+1, j] 上获得 dp[ i+1][ j ] 的优势 取走 nums[ j]，那么对手会在区间 [ i, j-1] 上获得 dp[ i][ j-1 ] 的优势 因此，当前玩家的最优选择是： dp[ i][ j] = max(nums[ i] - dp[ i+1][ j], nums[ j] - dp[ i][ j-1 ]) 步骤4：边界条件 当 i = j 时，只有一个数字，当前玩家只能取这个数字： dp[ i][ i] = nums[ i ] 步骤5：计算顺序 由于 dp[ i][ j] 依赖于 dp[ i+1][ j] 和 dp[ i][ j-1 ]，我们需要从小区间向大区间计算： 区间长度从 1 到 n 对于每个区间长度，遍历所有可能的起点 i 步骤6：最终判断 整个游戏的状态是 dp[ 0][ n-1]，如果 dp[ 0][ n-1 ] >= 0，则玩家1获胜（或平局），返回 true；否则返回 false。 步骤7：示例说明 以 nums = [ 1, 5, 2 ] 为例： dp[ 0][ 0] = 1, dp[ 1][ 1] = 5, dp[ 2][ 2 ] = 2 区间长度2： dp[ 0][ 1] = max(1-dp[ 1][ 1], 5-dp[ 0][ 0 ]) = max(1-5, 5-1) = max(-4, 4) = 4 dp[ 1][ 2] = max(5-dp[ 2][ 2], 2-dp[ 1][ 1 ]) = max(5-2, 2-5) = max(3, -3) = 3 区间长度3： dp[ 0][ 2] = max(1-dp[ 1][ 2], 2-dp[ 0][ 1 ]) = max(1-3, 2-4) = max(-2, -2) = -2 由于 dp[ 0][ 2] = -2 < 0，玩家1会输，返回 false。 这个解法的时间复杂度是 O(n²)，空间复杂度是 O(n²)，可以处理包含负数的数组。