摘要:
经典的状态机类型的dp问题。
题目
一个下标从 $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 。
示例 2:
输入:nums = [5,6,7,8]
输出:8
解释:最优子序列为 [8] ,交替和为 8 。
示例 3:
输入:nums = [6,2,1,2,4,5]
输出:10
解释:最优子序列为 [6,1,5] ,交替和为 (6 + 5) - 1 = 10 。
提示:
- $1 <= nums.length <= 10^5$
- $1 <= nums[i] <= 10^5$
动态规划
状态集合: 前 $i$ 个数字,数字总数为偶数的子序列与前 $i$ 个数字,数字总数为奇数的子序列构成的集合。
状态集合元素属性: 对于集合中的每个元素(子序列),定义子序列的交替和的最大值为元素属性。
状态计算: 设 $f[i][0]$ 为前 $i$ 个数字,数字总数为偶数的子序列的最大交替和;设 $f[i][1]$ 为前 $i$ 个数字,数字总数为奇数的子序列的最大交替和;
对前 $i$ 个数字依次计算两种交替和:
前 $i$ 个数字,子序列总数为偶数时,最后一个数字 $nums[i]$ 可取可不取。
取第 $i$ 个数字时,对于整个构成的子序列而言,由原数组前 $i - 1$ 个数字构成的子序列前部分总数一定是奇数,那么问题就变成了,由原数组前 $i - 1$ 个数字构成的总数为奇数的子序列的最大交替和与第 $i$ 项数字共同构成的子序列的最大交替和是多少。因为子序列下标从 $0$ 开始计算,取最后一项后总数是偶数,那么最后一项在子序列中的下标一定是奇数。由交替和的定义可知:
$f[i][0] = f[i - 1][1] - nums[i]$
不取第 $i$ 个数字时,我们从前 $i - 1$ 项来考虑。我们现在假设由原数组前 $i - 1$ 项构成的子序列总数是偶数,现在有第 $i$ 项存在,但是我们不取,那么原数组前 $i$ 项构成的子序列总数依然是偶数,且有:
$f[i][0] = f[i - 1][0]$
将上述两种情况合并有:
$f[i][0] = max(f[i - 1][0], f[i - 1][1] - nums[i])$
前i个数字,子序列总数为奇数时,最后一个数字 $nums[i]$ 也是可取可不取。
取第 $i$ 个数字时,这里又分为两种情况:
取了之后放弃子序列中所有前面的值,只留原数组第 $i$ 个数,总数依旧是奇数。
那么有:$f[i][1] = 0 + nums[i]$
取了之后保留子序列中所有前面的值,对于整个构成的子序列而言,由原数组前 $i - 1$ 个数字构成的子序列前部分总数一定是偶数,那么问题就变成了,由原数组前 $i - 1$ 个数字构成的总数为偶数的子序列的最大交替和与第 $i$ 项数字共同构成的子序列的最大交替和是多少。因为子序列下标从 $0$ 开始计算,取最后一项后总数是奇数,那么最后一项在子序列中的下标一定是偶数。由交替和的定义可知:
$f[i][1] = f[i - 1][1] + nums[i]$
将这两种子情况合并有:
$f[i][1] = max(0 + f[i - 1][1]) + nums[i]$
不取第 $i$ 个数字时,我们从前 $i - 1$ 项来考虑。我们现在假设由原数组前 $i - 1$ 项构成的子序列总数是奇数,现在有第 $i$ 项存在,但是我们不取,那么原数组前 $i$ 项构成的子序列总数依然是奇数,且有:
$f[i][1] = f[i - 1][1]$
将上述两种情况合并有:
$f[i][1] = max(f[i - 1][1], max(0 + f[i - 1][1]) + nums[i])$
1 | class Solution { |
仔细观察不难发现,dp数组每一项都是非负的(因为原数组每一项取值为$1 <= nums[i] <= 10^5$,且dp数组的初始项非负,且后序计算是不断地取最大值扩展的),那么 max(0ll, dp[i - 1][0]) + nums[i]
可以优化成 dp[i - 1][0] + nums[i]
.
原题链接: LeetCode 1911. 最大子序列交替和