題意
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])就是當前的最大。

?

轉載于:https://www.cnblogs.com/LQLlulu/p/8824959.html

總結

以上是生活随笔為你收集整理的HDU3415 Max Sum of Max-K-sub-sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。