完整題解：https://moon-jam.me/zerojudge_g278/

 

解題思路：

先從50%的測資數來想，k=1時應該怎麼做，這時要解的問題就變成，最大不重複子序列，可以再轉換成以第i為開頭往後幾項不重複！（最後再找多不重複的就好），可能還是不知道怎麼做嗎？

我的想法是從最後一項開始做，因為以最後一項為開頭，一定就只有一項不重複（因為它也沒有後面的了），接下來倒數第二項就是看他跟倒數第一項是不是一樣，倒數三項就是看它跟前兩項一不一樣，那倒數第i項要怎麼求呢？如果一項項比對會花到O(N^2)的時間，因此我這裡使用了一個資料結構，Queue，具體來說從n-1開始往前推(我使用0-base)，如果該項沒有出現在Queue中，就把那項推進去，而已那項為開頭的不重複連續子字串就會是Queue的長度（把自己推進去後），而如果發現自己的號碼就已經在裡面的話，就把Queue一項一項pop掉，直到Queue裡面沒有跟自己一樣的號碼，那要怎麼在O(1)時間內判斷自己有沒有在Queue內呢？可以自己先想一想，最後有給出一個方法，而如此一來因為Queue最多就是裝下n個數字，所以最多也就只會popn次，如此一來，就可以確定此方法能在O(n)內完成。

接下來要解決k ≠ 1的狀況，這邊我使用動態規劃，開一個dp[k][n]大小的陣列，dp[i][j]代表i個人從0～j可以吃多少的攤位，因此最後答案就會是dp[k][n-1]，首先我們可以先從前面提到k = 1將dp[1][j]全部填滿，接著因為i個人吃，最少就會有i個攤位，因此還會有dp[j][j-1]=j，接著接下來就可以進行狀態轉移了：

1. 假設dp[i][j]的第j不選

dp[i][j] = max(dp[i][j], dp[i][j-1])

2. 假設dp[i][j]的第j選

dp[i][j+len[j]-1] = max(dp[i+1][j+len[j]-1], dp[i][j-1]+len[j])

(len[i]表示以i為開頭的最大不重複子序列長度)

🌟可以開一個vis陣列，以vis[i]表示i有沒有在連續部分

🌟dp[1][j]可以在一開始推最大不重複子序列時先設定好部分內容

dp[1][j+num[j]-1]=max(dp[1][j+num[j]-1],num[j])

然後再利用動態規劃狀態轉移時dp[i][j] = max(dp[i][j], dp[i][j-1])完成整組dp[1][j]