本文主要是介绍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;}
}
这篇关于1911 最大子序列交替和（状态机DP）（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
