最大子序列交替和【LC1911】
一个下标从 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] 不是。
做了那么久怎么还是那么菜呢
- 思路：枚举选哪个【超时】
class Solution { public long maxAlternatingSum(int[] nums) { int n = nums.length; long[][] dp = new long[n][2];// 以nums[i]结尾的长度为偶数/奇数的子序列的最大交替和 dp[0][0] = -1;// 只有一个元素，不存在以其结尾长度为偶数的子序列 dp[0][1] = nums[0]; long res = 0L; for (int i = 1; i < n; i++){ dp[i][1] = nums[i];// 以当前元素作为第一个元素 for (int j = 0; j < i; j++){ dp[i][0] = Math.max(dp[i][0], dp[j][1] - nums[i]); dp[i][1] = Math.max(dp[i][1], dp[j][0] + nums[i]); res = Math.max(res, Math.max(dp[i][0], dp[i][1])); } } return res; } }
复杂度
- 时间复杂度：O(n2)
- 空间复杂度：O ( n )
思路：选或不选
每个元素可以延续在之前的元素后，此时会受下标奇数和偶数影响；也可以不选择，保留之前的最值。因此可以定义dp[i][0]表示前i个选了偶数个元素的最大值，dp[i][1]表示前i个选了奇数个元素的最大值
状态转移
dp[i][0]=dp[i−1][1]+nums[i]
dp[i][1]=dp[i−1][0]−nums[i]
优化：dp[i][0/1]定义的是到当前i这个元素为界限，并不意味着必须取i元素，只代表范围区间。
由于本题中选取子序列，并且不需要根据前一个元素的大小关系判断是否能接在末尾，所以状态定义是定义为截止当目前元素，选取的最大和【有点像背包的感觉，后续元素在前面元素的基础上判断选或不选，保留最大值】
类似不限制买卖次数、只持有一支股票的股票买卖，初始状态拥有一支股票，因此先卖再买再卖再买…求出最后拥有的最大现金值
- 定义状态：
dp[i][0]表示截止第i天，持有股票的最大现金数
dp[i][1]表示截止第i天，不持有股票的最大现金数
- 实现
class Solution { public long maxAlternatingSum(int[] nums) { int n = nums.length; long[][] dp = new long[n][2];// 在nums[0,i]选择长度为偶数/奇数的子序列的最大交替和 dp[0][0] = 0;// 只有一个元素，不存在以其结尾长度为偶数的子序列 dp[0][1] = nums[0]; for (int i = 1; i < n; i++){ dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - nums[i]); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + nums[i]); } return Math.max(dp[n - 1][0], dp[n - 1][1]); } }
复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
