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 。

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-alternating-subsequence-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首先，可以得出“最优子序列的长度一定为奇数”的结论，因为如果长度为偶数，去掉最后一位一定可以获得更大的“交替和”。

其次，最优子序列从下标1开始，偶数位的值一定大于奇数位。比如的最优子序列为，下标(偶数)的值大于下标(奇数)的值。

贪心地想，我们想让奇数下标的值尽可能小，偶数下标尽可能大。这一点联想到了 122. 买卖股票的最佳时机 II 这一题，这一题中奇数下标的值尽可能小对应题中买入价格尽可能低，偶数下标尽可能大对应题中卖出价格尽可能高，这一题最终选出的最优子序列对应题中选择的股票买入和卖出形成的序列。序列中奇数下标的数看做是买入价格，偶数位为卖出价格。对于下标为的数，将其看做卖出价格，那其买入价格呢，答案是。

通过以上分析，可以得知，如果将该题的输入前面加一个0，就可以采用122题的办法来解决。而题除了动态规划，还可以使用贪心，只要一个数大于前一个数，就贪心地将差值累加到利润中，关于题的解法可以看「这里」。下面使用题的贪心思路解决该题，想象输入数组前面加一个，不必真实添加，因为数组元素值大于，因此第一个数一定可以被累加，从第二个数开始，只要大于前一个数，就累加这个差值到答案中。

这种解法也是笔者偶然想到的，以上只是不严谨的推论，算法有效性的严格证明还未能给出，读者发现如有错误或者其余想交流的，欢迎大家留言评论。

值得一提的是，本题求的是“交替和”，如果是求最优子序列，这种解法就不适用了。

当然这一题常规思路还是动态规划，解法待补充。

代码

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long ans = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                ans += nums[i] - nums[i - 1];
            }
        }
        return ans;
    }
}