阿里巴巴找黄金宝箱(V)--滑动窗口

【阿里巴巴找黄金宝箱(V)】

一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0~N的箱子，每个箱子上面贴有一个数字。
阿里巴巴念出一个咒语数字k(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;
}