解題思路：

根據題目，我們所選的前後兩區間，必須符合：

1. 奇數偶數數量相同，即奇數偶數數量差為零。

2. 總和不超過 k。

3. 由於選過的數字必須刪除，可以視為前後兩區間不能重疊。

對於第一個條件，我們可以在掃描過程中，將奇數視為 +1，偶數視為 -1，

如此一來便可以透過計算前後區間的奇偶差之和是否為 0，得知所選奇數偶數數量是否相同。

對於第二個條件，只需要在符合其餘條件的所有可能組合中，尋找總和最接近 k 的組合即可。

而對於第三個條件，我們可以分開前半和後半兩個區間，

若前半從 1 開始往後選取到第 i 個數字，而後半從 n 開始往前選取到第 j 個數字，

只要判斷 i < j，即可得知兩區間是否重疊。

實作策略：

如果上述每個步驟都使用暴力迭代，複雜度肯定超時。

首先對於計算數字總和以及奇偶差之和的部分，可以透過預先建立前綴和的方式快速計算。

又由於需要檢查後面數來的區間，因此也需要做一組後綴和。

透過上述想法，可以得知我們需要儲存的資訊至少有

總和及奇偶差的前、後綴和。

接著是搜尋的部分，為了找出奇偶差可以互補的兩前後區間，

發現由於其為嚴格對應，若前半奇偶差為 d，則其只能和奇偶差為 -d 的區間配對，

我們可以直接利用一個二維陣列 gapMap，利用奇偶差當作索引，

將每個區間的資訊對應到其奇偶差的位置。

由於題目保證奇偶差最大不會超過 2000 ，因此 gapMap 大小只要開超過 4001 即可。

取得所有奇偶差合法的區間後，就可以透過二分搜起始結束位置，

再從中提出不重疊的所有不重疊的區間，

最後再對上一步的結果二分搜，找到總和最接近 k 的兩區間。

注意因為題目限制 a_i 只會有正整數，因此不論前綴後綴都會嚴格遞增，不須額外排序即可直接二分搜。

範例解法