1911. 最大子序列交替和

河流之所以能够到达目的地，是因为它懂得怎样避开障碍。

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)。