HDU3415 Max Sum of Max-K-sub-sequence

题意
given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

分析

先简化一下问题，不考虑环状，若有一个长度为n的序列，找出段连续的长度不超过k的子序列，使其连续和最大。若没有长度不超过K这个限制，那么就是简单的DP可以在On以内求出，但是加上这个条件，就无法用简单的DP求出了，因为不符合最优了。（当时考虑了一下若是加上一个状态转化为二维DP应该也可以做，但是时间复杂度不满足要求）。长度不超过K，可以想到滑动窗口，用一个递增单调队列来维护前缀和sum[maxn]。队首就是区间内的sum最小值，那么sum[i]-min(sum[j])就是当前的最大。