1911.最大子序列交替和

链接：1911.最大子序列交替和
难度：Medium
标签：数组、动态规划
简介：一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 。

题解 1 - cpp

• 编辑时间：2023-07-11
• 执行用时：328ms
• 内存消耗：149.5MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示以nums[i]结尾的时候，奇数和偶数时的最大结果。

class Solution {
public:
    typedef long long ll;
    ll maxAlternatingSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<ll>> dp(n, vector<ll>(2, 0));
        dp[0][0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - nums[i]);
        }
        return dp[n - 1][0];
    }
};

题解 2 - python

• 编辑时间：2023-07-11
• 执行用时：1092ms
• 内存消耗：30.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        even = nums[0]
        odd = 0
        for i in range(1, len(nums)):
            even, odd = max(even, odd + nums[i]), max(odd, even - nums[i])
        return even

题解 3 - rust

• 编辑时间：2023-07-11
• 执行用时：12ms
• 内存消耗：2.8MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
        let mut odd = 0;
        let mut even = nums[0] as i64;
        for i in 1..nums.len() {
            even = even.max(odd + nums[i] as i64);
            odd = odd.max(even - nums[i] as i64);
        }
        even
    }
}