LC.P1911[最大子序列交替和] 方法一:动态规划123456789101112131415161718class Solution { public long maxAlternatingSum(int[] nums) { int n = nums.length; // dp[i][0]表示以最后一个元素下标为偶数的子序列和 // 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) { for (int j = 0; j < 2; ++j) { 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 dp[n - 1][0]; }} 时间复杂度:$O(n)$ 空间复杂度:$O(n)$ 方法二:滚动数组(优化)12345678910class Solution { public long maxAlternatingSum(int[] nums) { long even = nums[0], odd = 0; for (int i = 1; i < nums.length; i++) { even = Math.max(odd + nums[i], even); odd = Math.max(even - nums[i], odd); } return even; }} 时间复杂度:$O(n)$ 空间复杂度:$O(1)$