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个位置，最大和为3+4+5=12（选择索引2,3,4）。其他选择如索引3,4,0（4+5+1=10）或索引4,0,1（5+1+2=8）或索引0,1,2（1+2+3=6）均小于12。
样例2：
输入：
nums = [8,2,3,4,5,6], k = 3输出：19解释：最大和为5+6+8=19（选择索引4,5,0）。其他选择如索引0,1,2（8+2+3=13）或索引1,2,3（2+3+4=9）或索引2,3,4（3+4+5=12）或索引3,4,5（4+5+6=15）均小于19。
样例3：
输入：
nums = [10,20,30,40], k = 2输出：70解释：最大和为30+40=70（选择索引2,3）。其他选择如索引0,1（10+20=30）或索引1,2（20+30=50）或索引3,0（40+10=50）均小于70。
约束条件
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= floor(nums.length / 2) （即k不超过数组长度的一半）
- 数组是环形的（索引0和n-1相邻）
程序代码
#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;
}
#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; }