C语言/数据结构算法题解：环形数组最大连续子段和——单调队列+前缀和O(n)解法-北京尧图网络

问题描述小明在玩一个环形数字游戏游戏规则是给定一个环形整数数组即首尾相连的数组每个元素代表一个位置上的“贡献值”。小明可以自由选择一段连续的位置由于是环形选择可以跨越数组首尾但被选中的位置总数不能超过数组长度的一半。小明想要最大化所选位置的贡献值之和。需要注意的是由于是环形数组当选择跨越首尾时实际选中的是数组末尾的一部分和开头的一部分组成的连续段。例如数组为 [1,2,3,4,5] 且允许选择3个位置那么一种可能的选择是 [5,1,2]即索引4,0,1。你的任务是帮助小明设计一个算法在 O(n) 时间复杂度内找到这个最大贡献值。测试样例样例1输入nums [1,2,3,4,5], k 3输出12解释允许选择3个位置最大和为34512选择索引2,3,4。其他选择如索引3,4,045110或索引4,0,15128或索引0,1,21236均小于12。样例2输入nums [8,2,3,4,5,6], k 3输出19解释最大和为56819选择索引4,5,0。其他选择如索引0,1,282313或索引1,2,32349或索引2,3,434512或索引3,4,545615均小于19。样例3输入nums [10,20,30,40], k 2输出70解释最大和为304070选择索引2,3。其他选择如索引0,1102030或索引1,2203050或索引3,0401050均小于70。约束条件1 nums.length 10^5-10^4 nums[i] 10^41 k floor(nums.length / 2) 即k不超过数组长度的一半数组是环形的索引0和n-1相邻程序代码#include stdio.h#include stdlib.h#include limits.hint maxContrib(int* nums, int numsSize, int k) {int n numsSize;// 构建双倍数组int* doubled (int*)malloc(2 * n * sizeof(int));for (int i 0; i 2 * n; i) {doubled[i] nums[i % n];}// 前缀和int* prefix (int*)malloc((2 * n 1) * sizeof(int));prefix[0] 0;for (int i 0; i 2 * n; i) {prefix[i 1] prefix[i] doubled[i];}// 单调队列维护前缀和的最小值索引int* deque (int*)malloc((2 * n 1) * sizeof(int));int head 0, tail 0;int ans INT_MIN;// 遍历右端点for (int i 1; i 2 * n; i) {// 移除超出窗口的索引while (head tail deque[head] i - k) {head;}// 如果队列不为空计算以 i-1 结尾的最大和if (head tail) {int sum prefix[i] - prefix[deque[head]];if (sum ans) ans sum;}// 维护单调递增队列while (head tail prefix[deque[tail - 1]] prefix[i]) {tail--;}deque[tail] i;}free(doubled);free(prefix);free(deque);return ans;}int main() {int nums1[] {1,2,3,4,5};printf(%d\n, maxContrib(nums1, 5, 3)); // 应输出12int nums2[] {8,2,3,4,5,6};printf(%d\n, maxContrib(nums2, 6, 3)); // 应输出19int nums3[] {10,20,30,40};printf(%d\n, maxContrib(nums3, 4, 2)); // 应输出70return 0;}#include stdio.h #include stdlib.h #include limits.h int maxContrib(int* nums, int numsSize, int k) { int n numsSize; // 构建双倍数组 int* doubled (int*)malloc(2 * n * sizeof(int)); for (int i 0; i 2 * n; i) { doubled[i] nums[i % n]; } // 前缀和 int* prefix (int*)malloc((2 * n 1) * sizeof(int)); prefix[0] 0; for (int i 0; i 2 * n; i) { prefix[i 1] prefix[i] doubled[i]; } // 单调队列维护前缀和的最小值索引 int* deque (int*)malloc((2 * n 1) * sizeof(int)); int head 0, tail 0; int ans INT_MIN; // 遍历右端点 for (int i 1; i 2 * n; i) { // 移除超出窗口的索引 while (head tail deque[head] i - k) { head; } // 如果队列不为空计算以 i-1 结尾的最大和 if (head tail) { int sum prefix[i] - prefix[deque[head]]; if (sum ans) ans sum; } // 维护单调递增队列 while (head tail prefix[deque[tail - 1]] prefix[i]) { tail--; } deque[tail] i; } free(doubled); free(prefix); free(deque); return ans; } int main() { int nums1[] {1,2,3,4,5}; printf(%d\n, maxContrib(nums1, 5, 3)); // 应输出12 int nums2[] {8,2,3,4,5,6}; printf(%d\n, maxContrib(nums2, 6, 3)); // 应输出19 int nums3[] {10,20,30,40}; printf(%d\n, maxContrib(nums3, 4, 2)); // 应输出70 return 0; }运行结果

C语言/数据结构算法题解：环形数组最大连续子段和——单调队列+前缀和O(n)解法

相关推荐

剪映专业版教程：制作特效与转场质感大片

为什么你的Illusion游戏Mod总在打架？用KKManager把它们管起来

让 AI 生成 SQL 前，先限制表、字段和扫描范围

更多资讯

React异步状态管理与电商分类导航实战

中药材原料选购全攻略：道地性、性价比与供应商选择

游戏脚本开发的法律风险与合规实践指南

权限与黑白名单：数据访问控制的分层设计与工程实践

开源同城跑腿小程序源码：从部署到二开的完整实战解析

Apache Calcite 1.4.0-incubating 发布解析：RelBuilder 关系代数构建器 API 的诞生

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？