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)。
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 ansif __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助力您的未来发展。
热门跟贴