1911 最大子序列交替和（状态机DP）（贪心）

题目

最大子序列交替和
一个下标从 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] 不是。

示例 1：

输入：nums = [4,2,5,3]
输出：7
解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。
示例 2：

输入：nums = [5,6,7,8]
输出：8
解释：最优子序列为 [8] ，交替和为 8 。
示例 3：

输入：nums = [6,2,1,2,4,5]
输出：10
解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105

DP

记忆化搜索

class Solution {
    private int[] nums;
    private long[][] cache;

    public long maxAlternatingSum(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        cache = new long[n][2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i],-1);
        }
        //最后一个数一定是偶数，如果是奇数还需要减去，不是最大和
        return dfs(n - 1, 0);
    }

    private long dfs(int i, int hold) {
        if (i < 0) {
            return 0;
        }
        if (cache[i][hold] != -1) {
            return cache[i][hold];
        }
        //设0代表偶数，1代表奇数
        if (hold == 1) {
            return cache[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - nums[i]);
        }
        return cache[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + nums[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

递推

class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[][] f = new long[n + 1][2];
        f[0][1] = 0;
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = Math.max(f[i][0], f[i][1] + nums[i]);
            f[i + 1][1] = Math.max(f[i][1], f[i][0] - nums[i]);
        }
        return f[n][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

空间优化

class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[] f = new long[2];
        for (int i = 0; i < n; i++) {
            long[] tmp = new long[]{f[0], f[1]};
            f[0] = Math.max(tmp[0], tmp[1] + nums[i]);
            f[1] = Math.max(tmp[1], tmp[0] - nums[i]);
        }
        return f[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

贪心

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long res = 0;
        //加入一个前驱下标pre，例如nums=[1,2,4]，变为nums=[0,1,2,4]
        int pre = 0;
        for (int num : nums) {
        	//如果有利润，那么res加上奇偶下标之差
            if (num > pre) {
                res += num - pre;
            }
            pre = num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15