【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])$

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].

原题链接： LeetCode 1911. 最大子序列交替和