這題我們可以試著用 dp 來解決他，定義 dp[i] 代表選擇第 i 個元素且總共選擇個數不超過 k 的最大值

則 dp[i] = max(sum(i, j)), for all i >= j >= i - k + 1

而 sum(i, j) 代表 [j, i] 這段區間的總和，我們也可以換成前綴和的寫法，定義 s[i] 為原序列前 i 項的總和，則

dp[i] = max(s[i] - s[j - 1]), for all i >= j >= i - k + 1

但是這樣轉移太慢了，所以我們想辦法優化一下

觀察後可以發現，要求最大的 s[i] - s[j - 1] ，也就是說對於 i 來說，他一定是從符合規定且最小的 j - 1 轉移過來的，所以我們只要維護 i >= j >= i - k + 1 當中最小的 s[j - 1] 就好了。

這樣就變成滑動視窗區間最小值問題了，用 deque 維護一下即可，均攤下來時間複雜度為 O(N)

不會維護的可以參考這篇文章 https://usaco.guide/gold/sliding-window?lang=cpp
裡面有講怎麼做 Sliding Window Minimum in O(N)

這題我們可以試著用 dp 來解決他，定義 dp[i] 代表選擇第 i 個元素且總共選擇個數不超過 k 的最大值

則 dp[i] = max(sum(i, j)), for all i >= j >= i - k + 1

而 sum(i, j) 代表 [j, i] 這段區間的總和，我們也可以換成前綴和的寫法，定義 s[i] 為原序列前 i 項的總和，則

dp[i] = max(s[i] - s[j - 1]), for all i >= j >= i - k + 1

但是這樣轉移太慢了，所以我們想辦法優化一下

觀察後可以發現，要求最大的 s[i] - s[j - 1] ，也就是說對於 i 來說，他一定是從符合規定且最小的 j - 1 轉移過來的，所以我們只要維護 i >= j >= i - k + 1 當中最小的 s[j - 1] 就好了。

這樣就變成滑動視窗區間最小值問題了，用 deque 維護一下即可，均攤下來時間複雜度為 O(N)

不會維護的可以參考這篇文章 https://usaco.guide/gold/sliding-window?lang=cpp
裡面有講怎麼做 Sliding Window Minimum in O(N)

果然是daniel play minecraft