题目描述

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

测试用例

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

思路

动态规划，参考代码中的注释👇

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入nums: ");
var nums = readline().split(",").map(Number);

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAlternatingSum = function (nums) {
  // 动态规划

  // 遍历nums，每次更新下面的两个值
  // 1. 此时形成的偶数长度子序列的最大交替和 even
  // 2. 所能形成的奇数长度子序列的最大交替和 odd

  // 初始化
  let even = 0; // 偶数
  let odd = nums[0]; // 奇数

  for (let i = 1; i < nums.length; i++) {
    even = Math.max(odd - nums[i], even);
    // console.log("even: ", even);
    odd = Math.max(even + nums[i], odd);
    // console.log("odd: ", odd);
  }

  return Math.max(even, odd);
};

const res = maxAlternatingSum(nums);
console.log("结果为: ", res);

/* 
  请输入nums:
  4,2,5,3
  结果为:  7

  请输入nums:
  5,6,7,8
  结果为:  8

  请输入nums:
  6,2,1,2,4,5
  结果为:  10
*/