我的解法是用單調隊列+dp

設 dp[i] = 陣列如果以 i 為結尾 的回頭程度最大值 (也就是說 題目所求就是 dp[n])

單調隊列裡面放的就是{i,j} i是pre[j]-dp[j-k] ，j 就是目前這個位置的下標

在假設我們要求的是 以dp[ i ]的話 那麼轉移式就會是 max(pre[i]-pre[i]+dp[i-k],pre[i]-pre[i-1]+dp[i-1-k]...,pre[i]-pre[i-t]+dp[i-t-k])

把 pre[i] 提出來，就會變成是 max(-pre[i]+dp[i-k],-pre[i-1]+dp[i-1-k],...,-pre[i-t]+dp[i-t-k]) 這樣就可以下去做了 或者是改成 min(pre[i]-dp[i-k],pre[i-1]-dp[i-1-k],...,pre[i-t]-dp[i-t-k])

然後要求的是一段區間的最大或是最小值就是砸單調對列就可以了!