1911. 最大子序列交替和 (opens new window)

1.动规

dp定义如下：

• dp[i][0]：表示nums第i个元素作为最大子序列的末尾元素，且在子序列索引为奇数时的最大交替和。
• dp[i][1]：表示nums第i个元素作为最大子序列的末尾元素，且在子序列索引为偶数时的最大交替和。

也就是说dp在维护时nums每个元素都会插入子序列，而对于nums[i]不插入时该如何表示？状态转移方程如下：

• dp[i][0]=Math.max(dp[0][1]，dp[1][1]...dp[i-1][1])-nums[i]
• dp[i][1]=Math.max(dp[0][0]，dp[1][0]...dp[i-1][0])+nums[i]

以dp[i][0]状态转移为例，更新时不能只计算前一个位置i-1的“末尾索引偶数的最大交替和”，而需要遍历计算前面每个位置插入后作为偶数索引的最大交替和，而如果这个最大值为dp[k][1](0<=k<i)，就表示[k+1,i-1]范围的数“不选”,nums[i]插入后的子序列为 {...nums[k]，nums[i] }

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long res=nums[0];
        long[][] dp=new long[nums.length][2];
        dp[0][0]=0;//奇数
        dp[0][1]=nums[0];//偶数
        long oddmax=dp[0][0],evenmax=dp[0][1];
        for(int i=1;i<nums.length;i++){
            dp[i][0]=evenmax-nums[i];
            dp[i][1]=oddmax+nums[i];
            oddmax=Math.max(dp[i][0],oddmax);
            evenmax=Math.max(dp[i][1],evenmax);
            res=Math.max(res,evenmax);
            res=Math.max(res,oddmax);
        }
        return res;
    }
}

2.优化

观察状态转移方程可以发现，每次更新只和前i-1个数的最大值有关，因此可以用两个变量维护dp中前i-1个结果的最大值。空间复杂度O(1)

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long res=nums[0];
        long oddmax=0,evenmax=nums[0];
        for(int i=1;i<nums.length;i++){
            long oddtemp=evenmax-nums[i];
            long eventemp=oddmax+nums[i];
            oddmax=Math.max(oddtemp,oddmax);
            evenmax=Math.max(eventemp,evenmax);
            res=Math.max(res,evenmax);
            res=Math.max(res,oddmax);
        }
        return res;
    }
}