力扣1911. 最大交替子序列和

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。比方说数组 [4,2,5,3] 的交替和为 (4 5) - (2 3) 4 。给你一个数组 nums 请你返回 nums 中任意子序列的 最大交替和 子序列的下标 重新 从 0 开始编号。一个数组的 子序列 是从原数组中删除一些元素后也可能一个也不删除剩余元素不改变顺序组成的数组。比方说[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列加粗元素但是 [2,4,2] 不是。示例 1输入nums [4,2,5,3]输出7解释最优子序列为 [4,2,5] 交替和为 (4 5) - 2 7 。代码classSolution{publiclongmaxAlternatingSum(int[]nums){long[][]dpnewlong[nums.length][2];dp[0][0]nums[0];dp[0][1]Long.MIN_VALUE;for(inti1;inums.length;i){dp[i][0]Math.max(dp[i-1][1]nums[i],Math.max(nums[i],dp[i-1][0]));dp[i][1]Math.max(dp[i-1][1],dp[i-1][0]-nums[i]);}returnMath.max(0,Math.max(dp[nums.length-1][0],dp[nums.length-1][1]));}}状态定义我们定义dp[i][j]表示从前i个数中选择一个子序列能得到的最大交替和。其中j只有两个取值0 或 1代表子序列末尾元素的特性dp[i][0]子序列的长度为奇数。这意味着最后一个元素的下标是偶数0, 2, 4…。根据题目要求这个元素是用来“加”的。dp[i][1]子序列的长度为偶数。这意味着最后一个元素的下标是奇数1, 3, 5…。根据题目要求这个元素是用来“减”的。状态转移方程对于第i个数nums[i]我们永远有两个选择选它或者不选它。(1) 更新dp[i][0]末尾是加号的状态如果不选nums[i]最大和维持前一个状态即dp[i-1][0]。如果选nums[i]它可以接在一个“减号状态”后面dp[i-1][1] nums[i]。它也可以作为子序列的第一个元素下标为 0nums[i]。结论dp[i][0] max(dp[i-1][0], dp[i-1][1] nums[i], nums[i])。(2) 更新dp[i][1]末尾是减号的状态如果不选nums[i]最大和维持前一个状态即dp[i-1][1]。如果选nums[i]它必须接在一个“加号状态”后面dp[i-1][0] - nums[i]。结论dp[i][1] max(dp[i-1][1], dp[i-1][0] - nums[i])。初始化dp[0][0] nums[0];dp[0][1] Long.MIN_VALUE;为什么dp[0][0]为nums[0]?万一nums[0]为负数呢为什么dp[0][0]不初始化为Math.max(0,nums[0])?这里的关键在于dp数组的含义我们定义dp数组为至少要选中一个数因此dp[0][0]nums[0]而dp[0][1]不合法。至于一个数都不选的情况直接放到return处判断一个数不选就是0不需要dp专门记录状态。