题目

一个下标从 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

解题思路分析

1、动态规划；时间复杂度O(n)，空间复杂度O(1)

func maxAlternatingSum(nums []int) int64 {
   n := len(nums)
   odd, even := 0, nums[0]
   for i := 1; i < n; i++ {
      odd, even = max(even-nums[i], odd), max(odd+nums[i], even)
   }
   return int64(even)
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、动态规划；时间复杂度O(n)，空间复杂度O(n)

func maxAlternatingSum(nums []int) int64 {
   n := len(nums)
   dp := make([][2]int, n)
   dp[0][0] = int(nums[0])
   dp[0][1] = 0
   for i := 1; i < n; i++ {
      dp[i][0] = max(dp[i-1][0], dp[i-1][1]+nums[i])
      dp[i][1] = max(dp[i-1][1], dp[i][0]-nums[i])
   }
   return int64(max(dp[n-1][0], dp[n-1][1]))
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、贪心法；时间复杂度O(n)，空间复杂度O(n)

func maxAlternatingSum(nums []int) int64 {
   // leetcode122.买卖股票的最佳时机II
   nums = append([]int{0}, nums...) // 补零
   res := 0
   for i := 1; i < len(nums); i++ {
      if nums[i] > nums[i-1] {
         res = res + nums[i] - nums[i-1]
      }
   }
   return int64(res)
}

总结

Medium题目，动态规划题目，如果在数组前面补个零等价于 leetcode122.买卖股票的最佳时机II