2026-08-11：距离至少为 K 的交替子序列的最大和。用go语言，给定一个整数数组和一个整数 k，你需要从中挑选一个下标严格递增的子序列。

2026-08-11：距离至少为 K 的交替子序列的最大和。用go语言，给定一个整数数组和一个整数 k，你需要从中挑选一个下标严格递增的子序列。挑选时必须满足相邻两个下标之差至少为 k。同时，这些下标对应的数值必须构成一个严格交替的序列：即要么按照“小、大、小、大……”的模式波动，要么按照“大、小、大、小……”的模式波动，相邻元素之间的大小关系交替变化且不能相等。只包含一个元素的子序列也视为合法交替。该子序列的得分定义为其中所有元素之和。请你计算在所有满足条件的子序列中，能够获得的最大得分。

1 <= n == nums.length <= 100000。

1 <= nums[i] <= 100000。

1 <= k <= n。

输入： nums = [5,4,2], k = 2。

输出： 7。

解释：

一种最优选择是下标 [0, 2]，对应的值为 [5, 2]。

距离条件成立，因为 2 – 0 = 2 >= k。

这些值严格交替，因为 5 > 2。

得分为 5 + 2 = 7。

题目来自力扣3915。

大体步骤如下： 1. 值域离散化

原数组中的数值范围可能较大（最大到 100000，但相对个数最多 100000），直接按值建立树状数组会浪费空间。因此先将所有数值排序、去重，得到一个紧凑的有序数组sorted。之后每个原始数值都可以用它在sorted中的下标（即排名）来表示，排名从0到m-1（m为不同值的个数）。这样就将值域压缩到了[0, m-1]的整数范围，便于树状数组处理。

2. 定义状态

对于每一个下标i，定义两种状态：

•fInc[i]：以nums[i]结尾、且子序列最后两项呈现递增关系（即前一个数 <nums[i]）的交替子序列的最大和。

•fDec[i]：以nums[i]结尾、且子序列最后两项呈现递减关系（即前一个数 >nums[i]）的交替子序列的最大和。

长度为 1 的子序列既可以视为“递增结尾”，也可以视为“递减结尾”，其和就是nums[i]本身。这两种状态覆盖了所有可能的交替模式（小大小大… 或 大小大小…）。

3. 初始化两个树状数组（Fenwick Tree）

树状数组用于维护值域区间内的最大 DP 值，支持单点取max更新和前缀最大值查询，每次操作均为O(log m)。

•inc树状数组：用于维护以递增结尾的状态fInc。为了能够方便地查询“值大于当前值”的所有状态，它在内部对索引进行了反转映射。

•dec树状数组：用于维护以递减结尾的状态fDec，采用原值域顺序，查询“值小于当前值”的状态。

两个树状数组大小均为m+1，使用 1‑based 索引。

4. 遍历数组，动态规划转移

按顺序遍历数组i = 0到n-1，对每个元素x = nums[i]执行以下子步骤：

4.1 距离约束的“延迟加入”

题目要求选中子序列的相邻下标之差 ≥ k。为了满足这一条件，我们采用延迟激活的策略：
只有当i ≥ k时，才将下标i-k对应的状态加入到树状数组中，使其可以被当前及之后的下标使用。这保证了转移来源的原始下标与当前下标的距离至少为k。

加入的具体操作为：

• 取出i-k位置已离散化的值j_prev（该值在之前遍历时已被替换为排名）。

• 更新inc：在位置m - j_prev上更新为max(原值, fInc[i-k])。
这一步利用了反转索引，把原本的“后缀查询”转化为树状数组擅长的“前缀查询”。

• 更新dec：在位置j_prev + 1上更新为max(原值, fDec[i-k])。

4.2 当前元素的离散化

在当前元素x上使用二分查找，得到其在sorted中的排名j（0‑based）。为了后续步骤i+k能够直接使用该排名而无需再次二分，将nums[i]就地修改为j（因为原值之后不再需要）。

4.3 计算当前状态

•计算fInc[i]：需要找一个前驱状态，它必须是递减结尾（fDec），且其对应的值严格小于x（即排名< j）。
在dec树状数组中查询前缀[1, j]（对应排名≤ j-1）的最大值，加上x即可得到fInc[i]。若不存在这样的前驱，查询返回0，则fInc[i] = x，对应单元素子序列。

•计算fDec[i]：需要找一个前驱状态，它是递增结尾（fInc），且其值严格大于x（即排名> j）。
通过反转索引，在inc树状数组中查询前缀[1, m-1-j]（对应排名≥ j+1）的最大值，加上x得到fDec[i]。

4.4 更新全局答案

用刚刚算出的fInc[i]和fDec[i]去更新全局最大得分ans。

5. 输出结果

遍历完整个数组后，ans即为所有满足条件的子序列的最大得分。

复杂度分析

•时间复杂度：
离散化排序O(n log n)；主循环执行n次，每次包含一次二分查找O(log m)和两次树状数组操作（更新/查询）均为O(log m)。由于m ≤ n，总时间复杂度为O(n log n)。

•额外空间复杂度：
离散化数组sorted占用O(m)；DP 数组fInc和fDec各占用O(n)；两个树状数组各占用O(m)。整体额外空间为O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
    "sort"
)

 type fenwick []int64

 func (f fenwick) update(i int, val int64) {
    for ; i < len(f); i += i & -i {
        f[i] = max(f[i], val)
    }
}

 // [1, i] 中的最大值
func (f fenwick) preMax(i int) (res int64) {
    for ; i > 0; i &= i - 1 {
        res = max(res, f[i])
    }
    return
}

 func maxAlternatingSum(nums []int, k int) (ans int64) {
    // 离散化 nums
    sorted := slices.Clone(nums)
    slices.Sort(sorted)
    sorted = slices.Compact(sorted)

     n := len(nums)
    fInc := make([]int64, n) // fInc[i] 表示以 nums[i] 结尾且最后两项递增的交替子序列的最大和
    fDec := make([]int64, n) // fDec[i] 表示以 nums[i] 结尾且最后两项递减的交替子序列的最大和

     // 值域树状数组
    m := len(sorted)
    inc := make(fenwick, m+1) // 维护 fInc[i] 的最大值
    dec := make(fenwick, m+1) // 维护 fDec[i] 的最大值

     for i, x := range nums {
        if i >= k {
            // 在这个时候才把 fInc[i-k] 和 fDec[i-k] 添加到值域树状数组中，从而保证转移来源的下标 <= i-k
            j := nums[i-k]
            inc.update(m-j, fInc[i-k]) // m-j 可以把后缀变成前缀
            dec.update(j+1, fDec[i-k])
        }

         j := sort.SearchInts(sorted, x)
        nums[i] = j // 注意这里修改了 nums[i]，这样上面的 nums[i-k] 无需二分

         fInc[i] = dec.preMax(j) + int64(x)     // 计算满足 nums[i'] < x 的 fDec[i'] 的最大值
        fDec[i] = inc.preMax(m-1-j) + int64(x) // 计算满足 nums[i'] > x 的 fInc[i'] 的最大值
        ans = max(ans, fInc[i], fDec[i])       // 枚举子序列以 nums[i] 结尾
    }

     return
}

 func main() {
    nums := []int{5, 4, 2}
    k := 2
    result := maxAlternatingSum(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List
import bisect

 class Fenwick:
    """树状数组，维护前缀最大值（1-indexed）"""
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)
        self.n = n

     def update(self, i: int, val: int) -> None:
        """将位置 i 的值更新为 max(tree[i], val)"""
        while i <= self.n:
            if val > self.tree[i]:
                self.tree[i] = val
            i += i & -i

     def pre_max(self, i: int) -> int:
        """查询 [1, i] 中的最大值"""
        res = 0
        while i > 0:
            if self.tree[i] > res:
                res = self.tree[i]
            i &= i - 1
        return res

 def max_alternating_sum(nums: List[int], k: int) -> int:
    # 离散化：获取去重排序后的数值
    sorted_nums = sorted(set(nums))
    m = len(sorted_nums)

     # 两个树状数组：
    # inc 维护 f_inc（以递增结尾的交替子序列最大和）
    # dec 维护 f_dec（以递减结尾的交替子序列最大和）
    inc = Fenwick(m)
    dec = Fenwick(m)

     n = len(nums)
    f_inc = [0] * n
    f_dec = [0] * n
    ans = 0

     for i, x in enumerate(nums):
        # 只有当下标距离至少为 k 时，才将 i-k 的状态加入树状数组
        if i >= k:
            j_prev = nums[i - k]          # 之前已经替换为离散化索引
            inc.update(m - j_prev, f_inc[i - k])
            dec.update(j_prev + 1, f_dec[i - k])

         # 当前元素离散化
        j = bisect.bisect_left(sorted_nums, x)
        nums[i] = j                       # 替换为索引，供后续使用

         # 计算以当前元素结尾的两种状态
        # f_inc: 之前递减结尾，且前一个数 < 当前数
        f_inc_i = dec.pre_max(j) + x
        # f_dec: 之前递增结尾，且前一个数 > 当前数
        f_dec_i = inc.pre_max(m - 1 - j) + x

         f_inc[i] = f_inc_i
        f_dec[i] = f_dec_i

         if f_inc_i > ans:
            ans = f_inc_i
        if f_dec_i > ans:
            ans = f_dec_i

     return ans

 if __name__ == "__main__":
    nums = [5, 4, 2]
    k = 2
    result = max_alternating_sum(nums, k)
    print(result)

C++完整代码如下：

  

  

  

using namespace std;

 class Fenwick {
    vector 
 
 tree; 
 
public:
    Fenwick(int n) : tree(n + 1, 0) {}

     // 更新位置 i（1-indexed）的值为 max(tree[i], val)
    void update(int i, long long val) {
        while (i < (int)tree.size()) {
            tree[i] = max(tree[i], val);
            i += i & -i;
        }
    }

     // 查询前缀 [1, i] 的最大值
    long long preMax(int i) const {
        long long res = 0;
        while (i > 0) {
            res = max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
};

 long long maxAlternatingSum(vector& nums, int k) {
    // 离散化
    vector sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();

     int n = nums.size();
    vector 
 
 fInc(n,  
 0), fDec(n, 0); // 注意初始化为 0（空子序列和为 0）

     Fenwick inc(m), dec(m); // 内部数组大小为 m+1，支持 1..m 索引
    long long ans = 0;

     for (int i = 0; i < n; ++i) {
        int x = nums[i];
        // 距离至少 k 时，将 i-k 的状态加入树状数组
        if (i >= k) {
            int j_prev = nums[i - k];          // 之前已替换为离散化索引
            inc.update(m - j_prev, fInc[i - k]);
            dec.update(j_prev + 1, fDec[i - k]);
        }

         // 当前元素的离散化索引
        int j = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
        nums[i] = j; // 替换原值，后续直接使用索引

         // 状态转移
        fInc[i] = dec.preMax(j) + x;         // 之前递减结尾，且前一个数 < 当前数
        fDec[i] = inc.preMax(m - 1 - j) + x; // 之前递增结尾，且前一个数 > 当前数

         ans = max({ans, fInc[i], fDec[i]});
    }

     return ans;
}

 int main() {
    vector nums = {5, 4, 2};
    int k = 2;
    long long result = maxAlternatingSum(nums, k);
    cout << result << endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。