1911 最大子序列交替和（状态机DP）（贪心）

本文主要是介绍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 <= 105
1 <= nums[i] <= 105

DP

记忆化搜索

class Solution {private int[] nums;private long[][] cache;public long maxAlternatingSum(int[] nums) {this.nums = nums;int n = nums.length;cache = new long[n][2];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}//最后一个数一定是偶数，如果是奇数还需要减去，不是最大和return dfs(n - 1, 0);}private long dfs(int i, int hold) {if (i < 0) {return 0;}if (cache[i][hold] != -1) {return cache[i][hold];}//设0代表偶数，1代表奇数if (hold == 1) {return cache[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - nums[i]);}return cache[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + nums[i]);}
}

递推

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

空间优化

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

贪心

class Solution {public long maxAlternatingSum(int[] nums) {long res = 0;//加入一个前驱下标pre，例如nums=[1,2,4]，变为nums=[0,1,2,4]int pre = 0;for (int num : nums) {//如果有利润，那么res加上奇偶下标之差if (num > pre) {res += num - pre;}pre = num;}return res;}
}