/*单调队列:单调队列即保持队列中的元素单调递增(或递减)的这样一个队列,可以从两头删除,只能从队尾插入. 队首为最优解,插入时从队尾插入。为了保证队列的单调性,我们从队尾开始删除元素,直到队尾元素比当前需要插入的元素优 因为它们已经不可能成为最优的元素了,因为当前要插入的元素位置比它们更优,值比它们更优*/ //长度不超过k的最大连续子序列 #include<cstdio> #include<algorithm> using namespace std; const int MAXN=100007; int sum[MAXN]; int queue[MAXN]; int main() { int T,id=0; scanf("%d",&T); while(T--) { int n,k,i,j,ans; scanf("%d%d",&n,&k); scanf("%d",sum+1); ans = sum[1] ; int fre=0,rea=0; queue[rea++] = 1; for(i=2;i<=n;i++) { scanf("%d",sum+i); while(i-queue[fre] >= k) { fre ++; } for(j=fre;j<rea;j++) { sum[ queue[j] ] += sum[i]; } while(rea>fre && sum[ queue[rea-1] ] <= sum[i]) { rea --; } queue[rea++] = i; ans = max(ans , sum[ queue[fre] ]); } printf("Case #%d: %d\n",++id,ans); } return 0; }