最大子序列交替和

难度: Medium

一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁵

Submission

运行时间: 792 ms

内存: 31.4 MB

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        ans=[]

        length=len(nums)
        if length==1:
            return nums[0]

        max_flag=True
        for i in range(length):
            if max_flag==True:
                if i==0 and nums[i]>nums[i+1] or i==length-1 and nums[i-1]<=nums[i]:
                    ans.append(nums[i])
                    max_flag=False
                    continue
                if i>0 and i<length-1: 
                    if nums[i]>=nums[i-1] and nums[i]>nums[i+1]:
                        ans.append(nums[i])
                        max_flag=False
                        continue
            else:
                if i==length-1 and nums[i-1]>nums[i]:
                    ans.append(nums[i])
                    max_flag=True
                    continue
                if i>0 and i<length-1: 
                    if nums[i]<nums[i-1] and nums[i]<=nums[i+1]:
                        ans.append(nums[i])
                        max_flag=True
                        continue
        if len(ans)%2==0:
            ans=ans[:-1]

        return sum(ans[::2])-sum(ans[1::2])

Explain

此题解采用了寻找局部峰值和谷值的策略，以此来构建一个最大交替和的子序列。具体方法是遍历数组，首先寻找局部最大值（峰），加入答案序列，并切换到寻找局部最小值（谷）的模式；然后寻找局部最小值，加入答案序列，并切换回寻找局部最大值的模式。这样做的逻辑基于峰值会贡献正值，谷值会贡献负值的想法。最后，如果构建的序列长度为偶数，则删除最后一个元素，因为偶数长度的序列最后一个元素将无法被抵消。最后计算交替和。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        ans=[]  # 用于存储选定的峰值和谷值

        length=len(nums)
        if length==1:
            return nums[0]  # 如果数组只有一个元素，直接返回该元素

        max_flag=True  # 标志位，用于指示当前是否在寻找峰值
        for i in range(length):
            if max_flag==True:  # 在寻找峰值的模式下
                if (i==0 and nums[i]>nums[i+1]) or (i==length-1 and nums[i-1]<=nums[i]):
                    ans.append(nums[i])  # 处理数组首尾的特殊情况
                    max_flag=False
                    continue
                if i>0 and i<length-1: 
                    if nums[i]>=nums[i-1] and nums[i]>nums[i+1]:
                        ans.append(nums[i])  # 处理一般情况的局部最大值
                        max_flag=False
                        continue
            else:  # 在寻找谷值的模式下
                if i==length-1 and nums[i-1]>nums[i]:
                    ans.append(nums[i])  # 处理数组末尾的特殊情况
                    max_flag=True
                    continue
                if i>0 and i<length-1: 
                    if nums[i]<nums[i-1] and nums[i]<=nums[i+1]:
                        ans.append(nums[i])  # 处理一般情况的局部最小值
                        max_flag=True
                        continue
        if len(ans)%2==0:
            ans=ans[:-1]  # 如果最后序列长度为偶数，移除最后一个元素

        return sum(ans[::2])-sum(ans[1::2])  # 计算最终的交替和

Explore

这种策略基于交替序列和的最大化原则。在任何连续的数字序列中，局部最大值代表该点可以收获最高的正贡献，而局部最小值则是最小的负贡献点。通过这种方式，我们可以确保每一个选择的峰值都能提供最大的正增益，而每一个谷值都尽可能减少损失。因此，通过在峰值和谷值之间交替，我们可以最大化整个序列的交替和。

数组的首尾元素需要特殊处理因为它们没有两边的邻居。对于数组的第一个元素，如果它比第二个元素大或者数组就这一个元素，它就是一个局部最大值；对于数组的最后一个元素，如果它比倒数第二个元素大，它也被视为一个局部最大值。这种处理确保了数组的边界被正确地考虑，不会因为缺少比较而错过可能的最大或最小值。

在交替序列中，最大化总和的关键是确保每个正值后面都有一个负值进行抵消。如果序列长度为偶数，意味着序列以正值结束，没有相应的负值来抵消这个正值。因此，为了保持交替和的最大化，需要移除最后一个元素，使得序列以负值结束，确保每个正值都有配对的负值。

题解中的条件语句主要用于确保局部最大值或最小值的正确判断。虽然在首次阅读时这些条件看起来可能有些冗余，但每个条件都针对不同的情况：数组的开头、结尾以及中间的元素。优化的空间可能存在于代码结构上，通过更清晰的条件划分或提取重复的逻辑为函数来增强代码的可读性和可维护性。不过，目前的多条件判断是必要的，以确保在所有可能的情况下都能正确识别出局部极值。