1911. Maximum Alternating Subsequence Sum

DP(MLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;

        long res = Long.MIN_VALUE;

        // 定义 dp[i][j] 为从前 i 个元素中选出的子序列结尾元素下标为偶数/奇数时的最大交替和
        long[][] dp = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - nums[i - 1]);

            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
        }

        return res;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;

        long f = 0, g = 0;
        for (int i = 1; i <= n; i++) {
            long ff = Math.max(f, g + nums[i - 1]);
            long gg = Math.max(g, f - nums[i - 1]);

            f = ff;
            g = gg;
        }

        return Math.max(f, g);
    }
}

References

1911. Maximum Alternating Subsequence Sum