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; }运行结果