【每日一题Day262】LC1911最大子序列交替和 | dp

最大子序列交替和【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 ( n 2 ) mathcal{O}(n^2) O(n2) 空间复杂度： O ( n ) mathcal{O}(n) O(n) 思路：选或不选 每个元素可以延续在之前的元素后，此时会受下标奇数和偶数影响；也可以不选择，保留之前的最值。因此可以定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示前 i i i个选了偶数个元素的最大值， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示前 i i i个选了奇数个元素的最大值 状态转移 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 1 ] + n u m s [ i ] d p [ i ] [ 1 ] = d p [ i − 1 ] [ 0 ] − n u m s [ i ] dp[i][0]=dp[i-1][1]+nums[i]\ dp[i][1]=dp[i-1][0]-nums[i] dp[i][0]=dp[i−1][1]+nums[i]dp[i][1]=dp[i−1][0]−nums[i] 优化： d p [ i ] [ 0 / 1 ] dp[i][0/1] dp[i][0/1]定义的是到当前 i i i这个元素为界限，并不意味着必须取 i i i元素，只代表范围区间。 由于本题中选取子序列，并且不需要根据前一个元素的大小关系判断是否能接在末尾，所以状态定义是定义为截止当目前元素，选取的最大和【有点像背包的感觉，后续元素在前面元素的基础上判断选或不选，保留最大值】 类似不限制买卖次数、只持有一支股票的股票买卖，初始状态拥有一支股票，因此先卖再买再卖再买…求出最后拥有的最大现金值 定义状态： d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示截止第 i i i天，持有股票的最大现金数 d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示截止第 i i 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 ) mathcal{O}(n) O(n) 空间复杂度： O ( n ) mathcal{O}(n) O(n)