1911. 最大子序列交替和

难度: 中等

来源: 每日一题 2023.07.11

---

一个下标从 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 <= 105
1 <= nums[i] <= 105

class Solution {
    public long maxAlternatingSum(int[] nums) {

    }
}

分析与题解

---

• 动态规划

  这个题目只有简简单单6行代码,但是我看不懂, 动态规划的入门看来要是首要任务了. 这题只能借助官方的题解了.....

  这个题的本质实际上就是动态规划. 动态规划的本质就是要找到状态转移方程.

  • 假设 dp[i][0] 代表着末位为偶数位的 最大值.

    • 若 nums[i] 被选择, 那么 dp[i][0] = dp[i - 1][1] + nums[i]
    • 否则 dp[i][0] = dp[i - 1][0]

  • 假设 dp[i][1] 代表着末位为奇数位的 最大值.

    • 若 nums[i] 被选择, 那么 dp[i][1] = dp[i - 1][0] - nums[i]
    • 否则 dp[i][0] = dp[i - 1][1]

  然后当 i = 0 时, nums[0][0] = nums[0], nums[0][1] = 0

  同时我们要知道一点就是如果末位是奇数,一定是减去,那么最终交替和肯定要比前一位的值计算的要小, 所以这里我们只考虑末位是偶数位的情况.

  所以在实现的过程中我们可以通过「滚动数组」的方式来进行空间优化。(PS: 不懂官方题解说明)

  最终,整个解题过程如下所示.

  class Solution {
      public long maxAlternatingSum(int[] nums) {
          long even = nums[0], odd = 0;
          for (int i = 1; i < nums.length; i++) {
              even = Math.max(even, odd + nums[i]);
              odd = Math.max(odd, even - nums[i]);
          }
          return even;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

  结果如下所示.