【阿里巴巴找黄金宝箱(V)】
一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地,藏宝地有编号从0~N的箱子,每个箱子上面贴有一个数字。
阿里巴巴念出一个咒语数字k(k<N),找出连续k个宝箱数字和的最大值,并输出该最大值。
输入描述
第一行输入一个数字字串,数字之间使用逗号分隔,例如: 2,10,-3,-8,40,5
字串中数字的个数>=1,<=100000;每个数字>=-10000,<=10000;
第二行输入咒语数字,例如:4,咒语数字大小小于宝箱的个数
输出描述
连续k个宝箱数字和的最大值,例如:39
示例1 输入输出示例仅供调试,后台判题数据一般不包含示例
输入
2,10,-3,-8,40,5 4
输出
39
示例2 输入输出示例仅供调试,后台判题数据一般不包含示例
输入
8 1
输出
8
方案1 暴力破解,时间复杂度O(n平方)
方案2 滑动窗体
方案2:窗口滑动,双指针移动,时间复杂度O(n),对于固定长度k,则起点第i个长度为k的总和:
* Sum(i) = Sum(i-1) - list[i-1] + list[i+k];
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
//方案1:暴力破解
int BaoLi(int *list, int n, int k)
{
int sum = 0;
int max;
for (int i = 0; i < n - k; i++) {
sum = 0;
for (int j = i; j < k + i; j++) {
sum += list[j];
}
if (i == 0) {
max = sum;
} else {
max = MAX(max, sum);
}
}
return max;
}
/*
*方案2:窗口滑动,双指针移动,对于固定长度,则起点第i个长度为k的总和:
* Sum(i) = Sum(i-1) - list[i-1] + list[i+k];
*/
int DoublePoint(int *list, int n, int k)
{
int sum = 0;
int max;
int left = 0;
int right = 0;
while (right < n) {
sum += list[right];
right++;
if (right - left < k) {
//滑窗大小不满足咒语数字则右边界继续向右滑动
continue;
}
if (left == 0) {
max = sum;
} else {
max = MAX(max, sum);
}
// 滑窗大小已经满足咒语数字,则左边界需要右移
sum = sum - list[left]; //公式:Sum(i) = Sum(i-1) - list[i-1] + list[i+k];
left++;
}
return max;
}
int main()
{
int list[100000] = {0};
char s[100001] = {0};
int k;
gets(s);
scanf("%d", &k);
char *p = strtok(s, ",");
int idx = 0;
while (p != NULL) {
list[idx] = atoi(p);
idx++;
p = strtok(NULL, ",");
}
printf("max1=%d\n", BaoLi(list, idx, k));
printf("max2=%d\n", DoublePoint(list, idx, k));
return 0;
}