VIRTUALS

the virtual labs for the virtuals

0%

【LeetCode双周赛55】C LeetCode 1911. 最大子序列交替和

摘要:
经典的状态机类型的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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
int n = nums.size();
// dp[i][0]: 前 i 个数,总数为偶数的子序列的最大交替和
// dp[i][1]: 前 i 个数,总数为奇数的子序列的最大交替和
vector<vector<long long>> dp(n, vector<long long>(2, 0));
dp[0][0] = 0, dp[0][1] = nums[0];
for (int i = 1; i < n; i++) {
// 考虑前i个数中子序列总数为偶数的情况
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - nums[i]);
// 考虑前i个数中子序列总数为奇数的情况
dp[i][1] = max(dp[i - 1][1], max(0ll, dp[i - 1][0]) + nums[i]);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};

仔细观察不难发现,dp数组每一项都是非负的(因为原数组每一项取值为$1 <= nums[i] <= 10^5$,且dp数组的初始项非负,且后序计算是不断地取最大值扩展的),那么 max(0ll, dp[i - 1][0]) + nums[i] 可以优化成 dp[i - 1][0] + nums[i].