1911. 最大子序列交替和
2023-07-10 本文已影响0人
红与树
河流之所以能够到达目的地，是因为它懂得怎样避开障碍。
LC每日一题，参考1911. 最大子序列交替和。
题目
一个下标从 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]不是。
输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。
输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。
输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。
解题思路
-
动态规划：由于题目要求子序列所以无法排序后贪心,考虑使用动态规划分解子问题,定义动态规划表示
[0,i]区间的最大序列交替和,需要末尾奇偶来判断是否加减当前数字,所以定义dp[i][0]表示[0,i]区间偶数结尾的最大交替和,dp[i][1]表示[0,i]区间以奇数结尾的最大交替和,转移方程见代码。
同时,可以优化空间到O(1).
动态规划
class Solution {
public long maxAlternatingSum(int[] nums) {
//子序列不能排序贪心 考虑动态规划
int n = nums.length;
//dp[i][0]表示[0,i]子序列偶数下标结尾的最大交替和 dp[i][1]表示结尾奇数
long[][] dp = new long[n][2];
//转移方程
dp[0][0] = nums[0];
dp[0][1] = 0;
for(int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][1] + nums[i],dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][0] - nums[i],dp[i-1][1]);;
}
//取最大
return Math.max(dp[n-1][0],dp[n-1][1]);
}
}
复杂度分析
- 时间复杂度：
O(n)，n为数组长度,一重循环遍历。 - 空间复杂度：
O(n)，动态规划使用记忆空间。
动态规划+优化空间
class Solution {
public long maxAlternatingSum(int[] nums) {
//子序列不能排序贪心 考虑动态规划
int n = nums.length;
//转移方程 优化空间
long even = nums[0],odd = 0;
for(int i = 1; i < n; i++) {
long tmp = even;
even = Math.max(odd+nums[i],even);
odd = Math.max(tmp-nums[i],odd);
//dp[i][0] = Math.max(dp[i-1][1] + nums[i],dp[i-1][0]);
//dp[i][1] = Math.max(dp[i-1][0] - nums[i],dp[i-1][1]);;
}
//取最大
return even; //贪心:以偶数结尾
}
}
复杂度分析
- 时间复杂度：
O(n)，n为数组长度,一重循环遍历。 - 空间复杂度：
O(1)。
