科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以 codeforces-go 仓库中 leetcode/weekly/299/c/README.md 的官方题解为主体完整讲解 LeetCode 第 299 场周赛 C 题「Maximum Score of Spliced Array」最大拼接数组得分的两种视角推导、四语言实现并结合仓库内同目录的 Go 实现、数据驱动测试文件与 copypasta/dp.go 中的算法笔记进行源码级印证。读完你不仅能掌握本题的 O(n) 解法还能理解把拼接/交换操作翻译成差分数组再套用最大子数组和这一可复用的建模套路。题目速览一次交换带来的最大收益题目给出两个长度相同的数组nums1与nums2。操作是在同一个下标区间[left, right]内把两个数组中对应位置的元素对调也可以不操作然后分别求两个数组的和答案取两者中的较大值。问这个最大得分是多少。本题的求解分为两步用数学推导把交换区间转化为差分数组上的区间和把选哪一段区间交换转化为最大子数组和问题用 Kadane 算法在 O(n) 内解决。核心推导把「交换一段区间」翻译成差分数组设数组长度为n定义$$ S_1 \sum\limits_{i}\textit{nums}_1[i] $$交换下标在[left, right]内的元素后新的nums₁的元素和可以写成原和 − 被换走的元素 换进来的元素$$ S_1 - (\textit{nums}_1[\textit{left}] \cdots \textit{nums}_1[\textit{right}]) (\textit{nums}_2[\textit{left}] \cdots \textit{nums}_2[\textit{right}]) $$合并相同下标上式变形为$$ S_1 (\textit{nums}_2[\textit{left}]-\textit{nums}_1[\textit{left}]) \cdots (\textit{nums}_2[\textit{right}]-\textit{nums}_1[\textit{right}]) $$这里出现了本题最关键的一步定义差分数组$$ \textit{diff}[i] \textit{nums}_2[i]-\textit{nums}_1[i] $$则交换后nums₁的和为$$ S_1 \textit{diff}[\textit{left}] \cdots \textit{diff}[\textit{right}] $$也就是说nums1的收益完全由diff数组的某个连续子段和决定。S1是常数为了最大化上式只需要最大化diff数组的最大子数组和。关键洞察问题等价于「最大子数组和」经过上述变换原题被归约为 LeetCode 经典题 53. 最大子数组和在一维数组中找出和最大的连续子数组。这里有两个细节值得注意子数组可以为空题目允许不交换即[left, right]可以是一个空区间。对应到差分视角就是可以不取任何diff元素。因此最大子数组和的下界是0初始化maxSum 0必不可少Kadane 状态转移定义f为以当前位置结尾的最大子段和状态转移为f max(f, 0) diff[i]再用maxSum max(maxSum, f)记录全局最大值。关于最大子数组和copypasta/dp.go 中保留了三种标准思路的注释可以互为印证Kadane 算法动态规划定义状态f[i]表示以a[i]结尾的最大子段和转移方程为f[i] max(f[i-1], 0) a[i]答案为max(f)前缀和视角遍历a的同时维护前缀和的最小值遍历到a[i]时当前最大子段和等于sum[i] - min(sum[j])j i。这一视角把最大子段和解释为前缀和的峰值与谷值之差本质上是低买高卖分治通常用于带修改的题目需要配合线段树维护区间最大子段和含最大前缀和、最大后缀和。本题采用的正是第一种Kadane视角这也是 README 题解中提到的前缀和做法背后等价的思想。对称性对 nums2 再做一遍上面只计算了交换后nums1能得到的最大和。但题目要求的是nums1与nums2两者中的较大者所以对nums2也要做一遍同样的计算对nums1求S1 maxSubarray(nums2 - nums1)即S1 maxSubarray(diff)对nums2求S2 maxSubarray(nums1 - nums2)即S2 maxSubarray(-diff)。最终答案是两者取最大值。由于diff与-diff的元素互为相反数两个方向的收益一般不同必须各算一次。四种语言实现以下是 README 题解中的完整实现与仓库内 leetcode/weekly/299/c/c.go 的 Go 代码逐行一致class Solution: def solve(self, nums1: List[int], nums2: List[int]) - int: max_sum f 0 for x, y in zip(nums1, nums2): f max(f, 0) y - x max_sum max(max_sum, f) return sum(nums1) max_sum def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) - int: return max(self.solve(nums1, nums2), self.solve(nums2, nums1))class Solution: def solve(self, nums1: List[int], nums2: List[int]) - int: max_sum f 0 for x, y in zip(nums1, nums2): if f 0: f 0 f y - x if f max_sum: max_sum f return sum(nums1) max_sum def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) - int: return max(self.solve(nums1, nums2), self.solve(nums2, nums1))class Solution { public int maximumsSplicedArray(int[] nums1, int[] nums2) { return Math.max(solve(nums1, nums2), solve(nums2, nums1)); } private int solve(int[] nums1, int[] nums2) { int s1 0; int maxSum 0; int f 0; for (int i 0; i nums1.length; i) { s1 nums1[i]; f Math.max(f, 0) nums2[i] - nums1[i]; maxSum Math.max(maxSum, f); } return s1 maxSum; } }class Solution { int solve(vectorint nums1, vectorint nums2) { int s1 0, max_sum 0, f 0; for (int i 0; i nums1.size(); i) { s1 nums1[i]; f max(f, 0) nums2[i] - nums1[i]; max_sum max(max_sum, f); } return s1 max_sum; } public: int maximumsSplicedArray(vectorint nums1, vectorint nums2) { return max(solve(nums1, nums2), solve(nums2, nums1)); } };func solve(nums1, nums2 []int) int { var s1, maxSum, f int for i, x : range nums1 { s1 x f max(f, 0) nums2[i] - x maxSum max(maxSum, f) } return s1 maxSum } func maximumsSplicedArray(nums1, nums2 []int) int { return max(solve(nums1, nums2), solve(nums2, nums1)) }几个实现要点solve中的s1在循环里累加省去一次sum(nums1)的额外遍历f max(f, 0) y - x把抛弃负收益前缀与累加差分值合为一步因为空子数组被允许maxSum初始为0这也是diff全为负数时答案仍为S1即不交换的原因。复杂度分析时间复杂度O(n)其中n是nums_i的长度——单次solve只需一次遍历总共调用两次空间复杂度O(1)——只使用常数个变量s1、maxSum、f甚至无需显式构造diff数组而是在循环中即时计算差分。仓库内的完整验证链路该题在仓库中不是孤立的一份题解而是有一套完整的实现 数据驱动测试链路实现leetcode/weekly/299/c/c.go 中的maximumsSplicedArray与 README 的 Go 代码完全一致测试入口leetcode/weekly/299/c/c_test.go 通过testutil.RunLeetCodeFuncWithFile(t, maximumsSplicedArray, c.txt, targetCaseNum)驱动测试测试数据leetcode/weekly/299/c/c.txt 以每fNumIn fNumOut行一组的纯文本格式存放用例即每 2 行输入 1 行输出为一组[60,60,60] [10,90,10] 210 [20,40,20,70,30] [50,20,50,40,20] 220 [7,11,13] [1,1,1] 31从 leetcode/testutil/leetcode.go 可以看到这套框架的实现细节RunLeetCodeFuncWithFile读取文本文件后按函数签名入参个数 返回个数将有效行分组parseRawArg负责把[60,60,60]这样的字符串解析为int切片随后通过反射调用目标函数并与期望输出比对leetcode/testutil/config.go 中DebugTLE默认2s用于在跑全量用例时检测超时。这些目录本身也来自仓库的自动生成能力从 copypasta/template/leetcode/generator_test.go 的TestWeekly/TestBiweekly可以看出仓库可借助LEETCODE_USERNAME_ZH、LEETCODE_PASSWORD_ZH等环境变量拉取对应周赛题目自动生成leetcode/weekly/id/下的目录、题解骨架与测试文件。用测试数据亲手验算结合c.txt中的三组数据可以直观地验证差分 Kadane 的推导用例 1nums1 [60,60,60]nums2 [10,90,10]。S1 180diff [-50, 30, -50]最大子数组和为30仅取diff[1]答案180 30 210。实际含义只交换下标1处的元素nums1变成[60,90,60]和为210。用例 2nums1 [20,40,20,70,30]nums2 [50,20,50,40,20]。S1 180diff [30,-20,30,-30,-10]最大子数组和为30 (-20) 30 40答案180 40 220对nums2反向计算同样得到220。用例 3nums1 [7,11,13]nums2 [1,1,1]。S1 31diff [-6,-10,-12]全部为负此时空子数组收益最大maxSum保持初始值0答案就是31即不交换是最优策略——这正是maxSum 0初始化的价值所在。在仓库中运行本题测试仓库当前目录结构下进入题目目录后执行标准 Go 测试命令即可cd leetcode/weekly/299/c go test -run Test_c -v其中Test_c通过 c_test.go 中targetCaseNum : 0 // -1控制测试范围0表示跑全部用例改为正数k表示只跑第k个用例-1表示跑最后一个用例RunLeetCodeFuncWithExamples会把负数映射到末位用例。变式与延伸这套建模还能用在哪里本题的建模——把数组变换/拼接操作翻译成差分再转化为最大子数组和——是一个高频套路在 copypasta/dp.go 的算法笔记中还能看到同族的延伸问题带收益映射的版本如求最大代价子串将字符按规则映射为代价后同样是最大子段和问题二维版本最大子矩阵问题可通过对行做前缀和压缩后逐列套用一维 Kadane带修改的版本若数组会动态变化Kadane 的一维线性扫描无法直接复用需要改用分治 线段树维护每个区间的最大前缀和、最大后缀和与最大子段和从而支持点修改后的快速查询。从 copypasta/dp.go 的注释还可以看到该仓库把子段长度有上限/下限等边界版本也做了归类前者借助单调队列后者通过维护前缀和最小值sum[i] - min(sum[j])i-j K实现与本题前缀和之差的视角一脉相承。小结LeetCode 周赛 299 的最大拼接数组得分一题核心价值在于两步建模差分数组把交换一段区间对总和的贡献写成diff数组的连续子段和Kadane / 最大子数组和在 O(n) 时间内求出最优交换区间并利用允许空子数组正确处理不交换的情形。配合 codeforces-go 仓库中 c.go、c.txt、c_test.go 与 testutil 数据驱动测试框架你可以完整复现从推导、实现到自动验证的全过程再结合 copypasta/dp.go 的算法笔记还能把这一套路推广到前缀和、二维、带修改等更广泛的变式问题。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解LeetCode 双周赛 135使差值相等的最小修改次数枚举 X 与差分数组两种解法codeforces go 题解LeetCode 双周赛 135使差值相等的最小修改次数枚举 X 与差分数组两种解法 本篇文章以 leetcode/bi科学计算codeforces-go 题解LeetCode 双周赛 102「数组所有前缀的得分」—— 前缀最大值与得分累计的单遍扫描codeforces go 题解LeetCode 双周赛 102「数组所有前缀的得分」—— 前缀最大值与得分累计的单遍扫描 导读 本文基于 leetcode/科学计算codeforces-go 实战贪心 最大堆 差分数组求解「零数组变换 III」力扣双周赛 144 C 题codeforces go 实战贪心 最大堆 差分数组求解「零数组变换 III」力扣双周赛 144 C 题 导读 本文基于 codeforces科学计算上一篇告别混乱代码nvim-lspconfig诊断配置完全指南下一篇Prometheus Node Exporter安全分析与改进建议创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考