1. 例题分析

题目描述

有 N 个数，围成一个圆圈 要你从中找出一段连续的 K 个数（在术语上，这连续的 K 个数称为这 N 个数的子段），使得这个子段的和最大。

输入格式

第一行 2 个正整数：N 和 K。

第二行 N 个 正整数 $a_i$

数据范围

1 <= N <= 100000

1 <= k <= N

1 <= $a_i$ <= 100000000

输出格式

一个整数，长度为 k 的最大子段和。

样例

6 3
9 2 6 4 5 3 7 1 13 4

26

题目分析

题目说了，这些数字是围成一个圈的，我们不妨把这个圈给画出来，方便理解。

然后，每 3 个相邻的数字抽出来，形成 1 个“子段” ，对这个求和，从中找出最大值，便是答案。我们把这个过程也一一列举出来。

要特别留意上图中的方案 9 和 10。如果这些数字并不是排成一个圆环，而是排成一条直线，那么就没有这个方案 9 和方案 10 。而因为数字围成一圈，就多了这两个候选方案了。如果我们不注意这个问题，那么我们枚举的过程中就枚举漏了一些情况，结果有可能就不正确了。

第二个问题是，当我们意识到有方案 9 和方案 10 之后，如何在代码上加以实现。大家留意一下截图中有一个 原始数列，对于方案 1 到方案 8 ，数字都能在 原始数列 的对应位置找得到数据（平行去找就可以），但是对于方案 9 和方案 10 ，平行去找会发现那个地方是空白的，如果不加以处理，就是数组越界访问了 ，这种错，一般就是提示 runtime error，你们提交程序的时候如果看到 runtime error，你们就是考虑数组是不是定义小了，是不是程序没控制好，下标越界，访问了数组以外的地方。

解决上面的问题很简单，就是把原始数据复制多一倍，然后就可以把环形问题变成直线问题去考虑了。有些同学可能会说，上面的过程不是只用多了一点点数据吗，完完整整拷贝一份会不会有点浪费？大家千万不要这么想，我向你们打包票，你们拷贝多一份，不会因此而内存不够的，也肯定不会导致超时，但是这样做省很多功夫，代码容易写，减少出错。如果你们在留意留意一下上面的题目，K 是变量，k 有可能等于 N 那么大，所以全量拷贝没毛病。

2. 完成程序

#include<bits/stdc++.h>
using namespace std;
int x[填空(1)];
long long sum[填空(2)],t;
int main()
{
	int n,k,i;
	long long MAX=0;
	scanf("%d %d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x[i]);
		x[ 填空(3) ] =x[i]; //复制多一份 
	}

	//计算前缀和数组 
	for(i=1;i<=填空(4);i++)
		sum[i] = sum[i-1] + x[i];
		
	//枚举各种方案 
	for(i=1; 填空(5) ;i++)
	{
		t = sum[ 填空(6)] - sum[i-1];
		MAX = max(MAX,t);
	}

	printf("%lld",MAX);

	return 0;
}

填空(1) : {{ input(1) }}

填空(2) : {{ input(2) }}

填空(3) : {{ input(3) }}

填空(4) : {{ input(4) }}

填空(5) : {{ input(5) }}

填空(6) : {{ input(6) }}