Week13 作业 E

题目描述：

给定一个环，A[1], A[2], A[3], … , A[n]，其中 A[1] 的左边是 A[n]。要求从环上找出一段长度不超过 K 的连续序列，使其和最大。

思路：

• 定义状态：F[i]表示以A[i]为结尾的最大值（A[i]必选）

• 状态表达式：F[i]=sum[i]-min{sum[j]}，其中i-K<j<i，sum表示前缀和，如此定义状态，就没有状态转移表达式，因为F[i]不能由F[i-1]得到，因为不知道F[i-1]的序列长度（信息不足）

• 边界条件：不需要，因为不需要状态转移

• 答案：max{F[i]}，可以进一步发现，F数组没有必要存储，边计算边更新答案即可

• 更进一步，发现A数组也没必要存储，因为前缀和数组可以在输入时计算出来

• 处理环形序列的方法：和石子排列一样的思想，把环变成线，添加冗余数据

使用单调队列优化状态表达式

• min{sum[j]}如果每次搜索都去查找，则每次搜索的复杂度是O(K)，可以发现，我们的sum[j]像滑动窗口一样在流动，可以使用一个递增的单调队列，队头每次都存储最小值

• 第i次迭代：取队头元素，计算F[i]（更新答案），弹出队列中过时元素，把sum[i]放进队列

^代码：

//进一步发现,a[i]的存储没有必要
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int a[2 * MAXN];
ll sum[2 * MAXN];
int main()
{
	int T; cin >> T;
	int N, K;
	while (T--)
	{
		memset(sum, 0, sizeof(sum));
		cin >> N >> K;
		for (int i = 1; i <= N; i++)
			scanf("%d", a + i);
		for (int i = 1; i <= N-1; i++)
			a[N + i] = a[i];
		N = N + K - 1;
		//calc prefixSum
		for (int i = 1; i <= N; i++)
			sum[i] = sum[i - 1] + a[i];
		//process
		ll ans = -1e10, l = 0, r = 0;
		deque<int> q;
		q.push_back(0);
		for (int i = 1; i <= N; ++i)
		{
			//把滑动窗口维护在当前元素的前面,而不是包括当前元素
			//因为迭代到i时,序列是必须选a[i]的,但是如果把滑动窗口包括了i,则可能出现sum[i]-sum[i]=0,没包括任何元素,很显然不符合预期
			if (sum[i] - sum[q.front()] > ans)
			{
				ans = sum[i] - sum[q.front()];
				l = q.front() + 1LL;
				r = i;
			}
			//维护递增队列,队头元素总是最小的;这里不是严格递增,能保证字典序
			while (!q.empty() && sum[q.back()] > sum[i])
				q.pop_back();
			//丢弃过期元素
			while (!q.empty() && q.front() <= i - K)	
				q.pop_front();
			q.push_back(i);
		}
		N = N + 1 - K;
		if (r > N) r = r - N;
		cout << ans << ' ' << l << ' ' << r << endl;
	}
	return 0;
}