2026-09-20：至多 K 次交换后最大子数组和。用go语言，给定一个由整数组成的序列 nums，以及一个整数 k。你最多可以进行 k 次位置调换，

2026-09-20：至多 K 次交换后最大子数组和。用go语言，给定一个由整数组成的序列 nums，以及一个整数 k。你最多可以进行 k 次位置调换，每次可任选两个位置，把这两个位置上的数互换。允许这样调整后，从序列中选出一段连续区间，把区间内所有数相加，求所有可能调整方式下，这个连续区间总和能达到的最大值，并返回该最大值。

1 <= nums.length <= 1500。

-100000 <= nums[i] <= 100000。

0 <= k <= nums.length。

输入： nums = [1,-1,0,2], k = 1。

输出： 3。

解释：

我们可以交换下标 1 和 3，得到数组 [1, 2, 0, -1]。

子数组 [1, 2] 的和为 3，这是在至多 k = 1 次交换后可能的最大子数组和。

题目来自力扣3962。

具体过程如下：

第一步：统计正数信息并做快速特判

首先遍历整个数组，统计所有正数的总和allPosSum以及正数的个数allPosCnt。
如果数组中一个正数都没有，那么任何子数组的和都不可能为正，最大值就是数组中最大的那个元素，直接返回即可。

如果存在正数，则尝试判断能否通过不超过 k 次交换，把所有正数都集中到一个连续的区间里。
因为正数一共有allPosCnt个，如果能把它们全部放进一个长度为allPosCnt的连续窗口中，那么该窗口内就全是正数，窗口和就是所有正数之和allPosSum，这显然是理论上的最大可能值。
于是用一个定长滑动窗口扫描整个数组，窗口长度固定为allPosCnt，统计窗口内正数的个数cnt。
如果某个窗口满足cnt + k >= allPosCnt，说明窗口外正数数量不超过 k，可以通过最多 k 次交换把它们全部换进窗口，同时把窗口内的非正数换出去。此时直接返回allPosSum。

第二步：无法一次收集全部正数时，准备数据结构

如果上面的特判不成立，说明无法通过 k 次交换把所有正数聚在一起，需要枚举所有可能的子数组，并计算每个子数组通过交换能达到的最大和。

为了高效处理“子数组内最小的若干负数”和“子数组外最大的若干正数”，算法对数组中的数值进行了离散化，并使用树状数组（Fenwick 树）来维护按值统计的数量和总和。
树状数组支持：添加/删除一个数，以及快速查询“前 k 小的数之和”。

一共使用三个树状数组：

•allPosTree：初始包含整个数组中所有正数，用于查询全局正数的数量和总和。

•negTree：动态维护当前枚举的子数组内部的负数。

•posTree：动态维护当前子数组外部的正数。每次枚举新的左端点时，它会从allPosTree复制一份作为初始状态。

第三步：双重循环枚举所有子数组

外层循环枚举子数组的左端点left。
对于每个left：

• 清空negTree，因为当前子数组内还没有负数。

• 将posTree重置为allPosTree的副本，表示子数组为空时，所有正数都在子数组外部。

• 初始化posSum = allPosSum，posCnt = allPosCnt，negCnt = 0，subSum = 0。

内层循环枚举右端点right，从left一直扩展到数组末尾，逐步把元素加入当前子数组：

• 每加入一个元素x，subSum增加x。

• 如果x是正数：它从“子数组外部”变成了“子数组内部”，所以从posTree中删除它，posSum减去x，posCnt减一。

• 如果x是负数：它进入了子数组，把它加入negTree，negCnt加一。

• 如果x是零：对和没有影响，也不需要参与交换，直接忽略。

此时，当前子数组是[left, right]，子数组内部有negCnt个负数，子数组外部有posCnt个正数。
允许最多 k 次交换。为了最大化子数组和，最优策略是：

• 从子数组内部挑出最负的若干个负数（即数值最小的负数）换出去；

• 从子数组外部挑出最大的若干个正数换进来。

交换次数不能超过 k，也不能超过子数组内负数的个数，也不能超过子数组外正数的个数。因此最多可以交换：
needSwap = min(negCnt, posCnt, k)。

如果needSwap > 0：

• 用negTree查询子数组内部最小的needSwap个负数之和，记为inSum。因为负数本身是负值，这个和越小（越负），换掉它们带来的收益越大。

• 用posTree查询子数组外部最小的posCnt - needSwap个正数之和，然后用posSum减去这个和，就得到了子数组外部最大的needSwap个正数之和，记为outSum。

• 交换带来的增量就是delta = outSum - inSum。由于inSum是负数，delta是正的提升。

• 如果needSwap == 0，则delta = 0。

最后，用subSum + delta更新全局最大值ans。

当所有左端点和右端点都枚举完毕后，ans就是经过最多 k 次交换后，可能得到的最大子数组和。

第四步：返回结果

返回全局最大值ans。

时间复杂度

• 统计正数和滑动窗口特判：O(n)。

• 离散化排序：O(n log n)。

• 初始化allPosTree：O(n log n)。

• 双重循环枚举所有子数组：共有 O(n²) 个子数组。对于每个子数组，需要更新树状数组以及查询前 k 小之和，每次操作 O(log n)。因此这部分是 O(n² log n)。

• 每次外层循环开始时，清空negTree和复制posTree需要 O(n) 时间，共 n 次，总 O(n²)。

• 综合来看，总时间复杂度为O(n² log n)。

额外空间复杂度

• 离散化数组、排名数组、树状数组等都需要 O(n) 的空间。

• 三个树状数组各占 O(n) 空间。

• 因此总额外空间复杂度为O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "math/bits"
    "slices"
    "sort"
)

 type pair struct{ cnt, sum int }
type fenwick struct {
    t       []pair
    sorted  []int
    highBit int
}

 func newFenwickTree(sorted []int) fenwick {
    n := len(sorted)
    return fenwick{
        t:       make([]pair, n+1),
        sorted:  sorted,
        highBit: 1 << (bits.Len(uint(n)) - 1),
    }
}

 // 添加 num 个 val，其中 val 离散化后的值为 i（i 从 1 开始）
// 如果 num < 0，表示减少 -num 个 val
// 注意 val = sorted[i-1]，无需手动传入
func (f *fenwick) update(i, num int) {
    val := f.sorted[i-1]
    for ; i < len(f.t); i += i & -i {
        f.t[i].cnt += num
        f.t[i].sum += num * val
    }
}

 // 返回前 k 小的数之和（k 从 1 开始）
func (f *fenwick) preSum(k int) (s int) {
    i := 0
    for b := f.highBit; b > 0; b >>= 1 {
        if nxt := i | b; nxt < len(f.t) && f.t[nxt].cnt < k {
            k -= f.t[nxt].cnt
            s += f.t[nxt].sum
            i = nxt
        }
    }
    // 加上等于第 k 小的数
    s += f.sorted[i] * k
    return
}

 func maxSum(nums []int, k int) int64 {
    // O(n) 特判：能否把正数都聚在一起
    allPosSum := 0
    allPosCnt := 0
    for _, x := range nums {
        if x > 0 {
            allPosSum += x
            allPosCnt++
        }
    }
    if allPosCnt == 0 { // 没有正数
        return int64(slices.Max(nums))
    }
    // 定长滑动窗口模板，窗口长度为 allPosCnt
    cnt := 0
    for i, x := range nums {
        if x > 0 {
            cnt++
        }
        left := i - allPosCnt + 1
        if left < 0 {
            continue
        }
        if cnt+k >= allPosCnt { // 可以把正数都聚在一起
            return int64(allPosSum)
        }
        if nums[left] > 0 {
            cnt--
        }
    }

     // 离散化
    n := len(nums)
    sorted := slices.Clone(nums)
    slices.Sort(sorted)
    sorted = slices.Compact(sorted)
    rank := make([]int, n)               // rank[i] 是 nums[i] 离散化后的值（从 1 开始）
    allPosTree := newFenwickTree(sorted) // 包含所有正数的树状数组
    for i, x := range nums {
        rank[i] = sort.SearchInts(sorted, x) + 1
        if x > 0 {
            allPosTree.update(rank[i], 1)
        }
    }

     negTree := newFenwickTree(sorted)
    posTree := newFenwickTree(sorted)
    ans := math.MinInt

     // 枚举子数组左端点
    for left := range nums {
        clear(negTree.t)
        copy(posTree.t, allPosTree.t)
        posSum := allPosSum
        posCnt := allPosCnt
        negCnt := 0
        subSum := 0

         // 枚举子数组右端点
        for right := left; right < n; right++ {
            // x 从子数组外移到子数组内
            x := nums[right]
            rk := rank[right]
            subSum += x
            if x > 0 {
                posTree.update(rk, -1)
                posSum -= x
                posCnt--
            } else if x < 0 {
                negTree.update(rk, 1)
                negCnt++
            }

             // 计算通过交换导致的元素和的增量
            delta := 0
            needSwap := min(negCnt, posCnt, k)
            if needSwap > 0 {
                inSum := negTree.preSum(needSwap)
                outSum := posSum - posTree.preSum(posCnt-needSwap)
                delta = outSum - inSum
            }

             ans = max(ans, subSum+delta)
        }
    }

     return int64(ans)
}

 func main() {
    nums := []int{1, -1, 0, 2}
    k := 1
    result := maxSum(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

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

 from bisect import bisect_left

 class Fenwick:
    def __init__(self, vals):
        self.vals = vals
        n = len(vals)
        self.cnt = [0] * (n + 1)
        self.sums = [0] * (n + 1)
        self.high_bit = 1 << (n.bit_length() - 1) if n else 0

     def update(self, i, num):
        val = self.vals[i - 1]
        n = len(self.cnt)
        while i < n:
            self.cnt[i] += num
            self.sums[i] += num * val
            i += i & -i

     def pre_sum(self, k):
        if k <= 0:
            return 0

         i = 0
        s = 0
        b = self.high_bit
        cnt = self.cnt
        sums = self.sums

         while b:
            nxt = i | b
            if nxt < len(cnt) and cnt[nxt] < k:
                k -= cnt[nxt]
                s += sums[nxt]
                i = nxt
            b >>= 1

         s += self.vals[i] * k
        return s

 def max_sum(nums, k):
    all_pos_sum = 0
    all_pos_cnt = 0

     for x in nums:
        if x > 0:
            all_pos_sum += x
            all_pos_cnt += 1

     if all_pos_cnt == 0:
        return max(nums)

     cnt = 0
    for i, x in enumerate(nums):
        if x > 0:
            cnt += 1

         left = i - all_pos_cnt + 1
        if left < 0:
            continue

         if cnt + k >= all_pos_cnt:
            return all_pos_sum

         if nums[left] > 0:
            cnt -= 1

     n = len(nums)
    vals = sorted(set(nums))
    rank = [bisect_left(vals, x) + 1 for x in nums]

     all_pos_tree = Fenwick(vals)
    for i, x in enumerate(nums):
        if x > 0:
            all_pos_tree.update(rank[i], 1)

     neg_tree = Fenwick(vals)
    pos_tree = Fenwick(vals)

     m = len(vals)
    ans = -10**30

     for left in range(n):
        neg_tree.cnt = [0] * (m + 1)
        neg_tree.sums = [0] * (m + 1)

         pos_tree.cnt = all_pos_tree.cnt[:]
        pos_tree.sums = all_pos_tree.sums[:]

         pos_sum = all_pos_sum
        pos_cnt = all_pos_cnt
        neg_cnt = 0
        sub_sum = 0

         for right in range(left, n):
            x = nums[right]
            rk = rank[right]

             sub_sum += x

             if x > 0:
                pos_tree.update(rk, -1)
                pos_sum -= x
                pos_cnt -= 1
            elif x < 0:
                neg_tree.update(rk, 1)
                neg_cnt += 1

             need_swap = min(neg_cnt, pos_cnt, k)
            delta = 0

             if need_swap > 0:
                in_sum = neg_tree.pre_sum(need_swap)
                out_sum = pos_sum - pos_tree.pre_sum(pos_cnt - need_swap)
                delta = out_sum - in_sum

             ans = max(ans, sub_sum + delta)

     return ans

 if __name__ == "__main__":
    nums = [1, -1, 0, 2]
    k = 1
    print(max_sum(nums, k))

C++完整代码如下：

  

  

    

  


 using namespace std;

 struct Pair {
    int cnt;
    int sum;
    Pair(int c = 0, int s = 0) : cnt(c), sum(s) {}
};

 struct Fenwick {
    vector 
 
 t; 
 
    vector sorted;
    int highBit;

     Fenwick() {}
    Fenwick(const vector& sorted_) : sorted(sorted_) {
        int n = sorted.size();
        t.assign(n + 1, Pair(0, 0));
        highBit = 1;
        while (highBit * 2 <= n) highBit *= 2;
    }

     void update(int i, int num) {
        int val = sorted[i - 1];
        for (; i < (int)t.size(); i += i & -i) {
            t[i].cnt += num;
            t[i].sum += num * val;
        }
    }

     int preSum(int k) {
        int i = 0;
        int s = 0;
        for (int b = highBit; b > 0; b >>= 1) {
            int nxt = i | b;
            if (nxt < (int)t.size() && t[nxt].cnt < k) {
                k -= t[nxt].cnt;
                s += t[nxt].sum;
                i = nxt;
            }
        }
        s += sorted[i] * k;
        return s;
    }
};

 long long maxSum(vector& nums, int k) {
    int allPosSum = 0;
    int allPosCnt = 0;
    for (int x : nums) {
        if (x > 0) {
            allPosSum += x;
            allPosCnt++;
        }
    }
    if (allPosCnt == 0) {
        return *max_element(nums.begin(), nums.end());
    }

     int cnt = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        if (x > 0) cnt++;
        int left = i - allPosCnt + 1;
        if (left < 0) continue;
        if (cnt + k >= allPosCnt) {
            return allPosSum;
        }
        if (nums[left] > 0) cnt--;
    }

     // 离散化
    vector sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();
    vector rank(n);
    for (int i = 0; i < n; i++) {
        rank[i] = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
    }

     Fenwick allPosTree(sorted);
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            allPosTree.update(rank[i], 1);
        }
    }

     Fenwick negTree(sorted);
    Fenwick posTree(sorted);
    long long ans = LLONG_MIN;

     for (int left = 0; left < n; left++) {
        // 清空 negTree
        fill(negTree.t.begin(), negTree.t.end(), Pair(0, 0));
        // 复制 allPosTree 到 posTree
        posTree.t = allPosTree.t;

         int posSum = allPosSum;
        int posCnt = allPosCnt;
        int negCnt = 0;
        int subSum = 0;

         for (int right = left; right < n; right++) {
            int x = nums[right];
            int rk = rank[right];
            subSum += x;
            if (x > 0) {
                posTree.update(rk, -1);
                posSum -= x;
                posCnt--;
            } else if (x < 0) {
                negTree.update(rk, 1);
                negCnt++;
            }

             int delta = 0;
            int needSwap = min({negCnt, posCnt, k});
            if (needSwap > 0) {
                int inSum = negTree.preSum(needSwap);
                int outSum = posSum - posTree.preSum(posCnt - needSwap);
                delta = outSum - inSum;
            }

             ans = max(ans, (long long)subSum + delta);
        }
    }

     return ans;
}

 int main() {
    vector nums = {1, -1, 0, 2};
    int k = 1;
    long long result = maxSum(nums, k);
    cout << result << endl;
    return 0;
}

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