Medium

题目描述

0索引数组的交替和定义为偶数索引元素之和减去奇数索引元素之和。

例如，[4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4。

给定一个数组 nums，返回 nums 任意子序列的最大交替和（重新索引子序列元素后）。

数组的子序列是通过删除原数组的一些元素（可能不删除）而不改变剩余元素相对顺序生成的新数组。例如，[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 <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这是一道经典的动态规划问题。关键观察是我们需要追踪两种状态：

  1. 当前元素作为偶数位置（加法项）
  2. 当前元素作为奇数位置（减法项）

状态定义：

  • even：表示以当前位置结束，且当前元素作为偶数索引的最大交替和
  • odd：表示以当前位置结束，且当前元素作为奇数索引的最大交替和

状态转移： 对于每个元素 nums[i]，我们有以下选择：

  1. 将其作为偶数位置元素：new_even = max(even, odd + nums[i])

    • 要么继续之前的偶数状态（不选当前元素）
    • 要么从奇数状态转换过来（选择当前元素作为新的偶数位置）

  2. 将其作为奇数位置元素：new_odd = max(odd, even - nums[i])

    • 要么继续之前的奇数状态
    • 要么从偶数状态转换过来（选择当前元素作为新的奇数位置）

优化空间： 由于只需要前一个状态，可以用两个变量代替数组，空间复杂度降为O(1)。

代码实现

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        long long even = 0, odd = 0;
        
        for (int num : nums) {
            long long newEven = max(even, odd + num);
            long long newOdd = max(odd, even - num);
            even = newEven;
            odd = newOdd;
        }
        
        return even;
    }
};

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

public class Solution {
    public long MaxAlternatingSum(int[] nums) {
        long even = 0, odd = 0;
        
        foreach (int num in nums) {
            long newEven = Math.Max(even, odd + num);
            long newOdd = Math.Max(odd, even - num);
            even = newEven;
            odd = newOdd;
        }
        
        return even;
    }
}

var maxAlternatingSum = function(nums) {
    let even = 0, odd = 0;
    
    for (let num of nums) {
        let newEven = Math.max(even, odd + num);
        let newOdd = Math.max(odd, even - num);
        even = newEven;
        odd = newOdd;
    }
    
    return even;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历数组一次，每个元素处理时间为O(1)
空间复杂度O(1)只使用两个变量存储状态

相关题目