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

这篇具有很好参考价值的文章主要介绍了【每日一题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;
    }
}

复杂度
- 时间复杂度： $\mathcal{O}(n^2)$
- 空间复杂度： $\mathcal{O}(n)$

思路：选或不选

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

实现文章来源地址https://www.toymoban.com/news/detail-550541.html

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]);
    }
}