hdu 3415 题意：给出n个整数，是一个环（也就是a[n]右边是a[1]）求一段长度不超过k的数使得和最大，问最大和是多少并给出这段数的位置。 思路：为了处理环，先把n个数复制一下就好，然后求前缀和sum[i] 由于区间[l,r]的和可以用前缀和表示为sum[r]-sum[l-1] 因此在区间长度小于等于k的前提下，我要求sum[r]-sum[l-1]的最大值，如果我们考虑把端点r固定，那么就是要求[l-1,r-1]中的sum的最小值。 因此我们考虑用单调队列来维护sum[i-k]到sum[i-1]的最小值。 我们的做法是：枚举区间右端点i，同时用单调队列维护i之前的k个数[i-k,i-1]的最小值。 由于要求“If there …

ural 1126 题意：n个数，求从第k个元素开始，求每k个元素的最大值（一共求n-k+1次） 思路：单调队列。 单调队列学习链接 其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333 说下我的理解： 单调队列的尾端（就是后进入元素的那一端）其实和单调栈类似。 首端加了个元素期限的概念，不断删除“过期”的元素。 所谓过期的元素，对于这道题来说，当我往前移动到第k+1个元素的时候，第1个元素就是过期了的元素，堆答案不会再有贡献。 理论上单调队列中的元素是<元素的期限，元素>的二元组。 而一般元素的"期限"是由下标的位置决定的，而得到下标就可以知道元素。 所以我们实际操 …

Sliding Window 看这个问题：An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position.Your task is to determine the maximum and …