: http://0rz.tw/fLPOZ
: 題目PDF如上
又來問這張考卷>"<
想請問題號V.a.2
題目說要用O(n^2)的時間
以一個雙邊queue(dequeue)製造max alternative sum

我是先選最大的pop之後再挑最小的pop 然後重複 剛好O(n^2) 你那樣的作法也是可以不過題目的input應該是一個deque吧?

題目說要對given deque做 你這樣的做法感覺破壞了原本的deque 而且也不一定能夠在原本的deque做出這樣的sequence？一樓的做法不就是題目給的greedy嗎？

這題應該要 DP 吧

我是挑整個deque的最大最小 題目是看兩個end的元素先取較大的再取較小的

定義dp[a][b]為從a到b所能得的最大alternative sumdp[a][b] = max{in[a]+dp[a+1][b], in[b]+dp[a][b-1]}表格: n^2格 ， 每格要查另外兩格得到答案 時間O(n^2)_recurrence、boundary condition還要看現在要加還是減寫的時候寫仔細點別漏掉就好題目的deque是給定的，不能改變裡面的順序a的話 隨便給個反例就行了 ex. {5,3,1,2,4}

你這樣定義 dp[a][b] 要怎麼考慮 alternative?

樓上的疑問是...？定義不清楚嗎？看dp[a][b]是第幾次要取的數字 來決定這次要加還是減要減的話 在上面in[a]、in[b]前面加上"-"就好