這題預期的解法是使用兩條 deque 來達到 $\color{black}{O(n)}$ 的時間複雜度。設 $\color{black}{i_1 = k}$ 時 $\color{black}{\sigma(\mathbf{i}; \mathbf{a})}$ 的最大值為 $\color{black}{D_k}$，則我們的答案就是

\[\color{black}{S = \max_{1\le k\le n}D_k}.\]

為了接下來的討論方便，定義 $\color{black}{d_k}$ 為「當 $\color{black}{i_1 = k}$ 時，$\color{black}{\sigma(\mathbf{i}; \mathbf{a})}$ 的最小值」。首先觀察

\[\color{black}{\sigma(\mathbf{i}; \mathbf{a}) = a_{i_1} - a_{i_2} + a_{i_3} - a_{i_4} + \ldots = a_{i_1} - \sigma(i_2, i_3, \ldots, i_m; \mathbf{a}),}\]

因此有

\[\color{black}{D_k = a_k - \min\left\{\min_{k+1\le l\le k+\delta}\{d_l\}, 0\right\},}\]

以及

\[\color{black}{d_k = a_k - \max\left\{\max_{k+1\le l\le k+\delta}\{D_l\}, 0\right\}.}\]

直接使用上兩式計算會得到 $\color{black}{\Theta(\delta n)}$ 時間的演算法。但由於求最小最大值的區間左右界是單調的，可以使用 deque 來得到 $\color{black}{O(n)}$ 時間的演算法，並在時間限制內通過。這種利用 deque 來降低時間複雜度的技巧相當有名，讀者可以搜尋「sliding window minimum」以找到更多資料。

然後看到有人用 $\color{black}{\log n}$ 資料結構 AC 這題 (TдT)