o079. 4. 最佳選擇

 題目描述：

給一個長度為 n 的正整數序列 a1,a2...an ，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。

求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。

這題步驟比較多，簡單來說，怎麼選都是前面選幾個，後面選幾個，將總和加起來，所以第一步要先得出前後綴和。：

假設測資a1...an分別是1,2,3,4,5,6

1.先算出前後綴和pre = [1,3,6,10,15,21] , ends = [6,11,15,18,20,21]，

再來就是前後綴合的組合囉，想法是這樣，我們取出pre[0]去跟ends的每一個結合看看，可以結合的標準是範圍不重複，且奇偶數個數相同，且總和不超過k，的可能中求最大，先別管時間問題了，光要做這件事情，我們就必須在算前後綴和時，順便紀錄了每一個前後綴合的奇偶數個數，我把前綴和記錄成這樣：

pre = [[0,0],[1,-1],[3,0],[6,-1],[10,0],[15,-1],[21,0]]，這代表組成21的時候奇偶個數沒差別，15的時候奇偶個數差1。

再來end我記成這樣：

endIndex = {1: [-5, -3, -1], 0: [-4, -2, 0]}

endSum = {1: [6, 15, 20], 0: [11, 18, 21]}

代表偶數比奇數多一個的後綴和有6,15,20其最左邊的資料在第5,3,1個位置，解釋一下，以20為例，20是2,3,4,5,6相加的結果，其中，偶數多奇數一個，且資料起始位置是1(2在a的第一個位置)，補充一下，為什麼5,3,1記成-5,-3,-1，因為我希望保持結構是升序排序，那麼我後面做二分搜的時候比較容易。

所以有了pre,endIndex,endSum之後該怎麼做呢，依樣，依序取出pre的每一個資料，假設拿到pre[1]，那麼因為pre[1]又等於[1,-1]，其中1代表前綴和是1，1代表取到第一個位置，-1代表奇偶差是1，所以我們要的資料就是在endIndex[1],endSum[1]之中，那要怎麼快速找到位置不重複，且相加小於k的資料呢，這邊我們就是用二分搜了，我很懶，直接用工具了。

上面這段說明，記得跟一下文字的標色，會比較好閱讀。

以下是完整程式碼：

import bisect
n,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]

pre = [[0,0]]
for i in range(0,len(d)):
    if d[i] % 2 == 0: 
        p = 1
    else:
        p = -1
    last = pre[-1]
    pre.append([last[0]+d[i] , last[1]+p])
    
ends = 0
endoe = 0
endSum = {}
endIndex = {}
for i in range(len(d)-1 , -1 , -1):
    if d[i] % 2 == 0: 
        endoe += 1
    else:
        endoe += -1
    ends += d[i]
    if endoe in endSum:
        endSum[endoe].append(ends)
        endIndex[endoe].append(-i)
    else:
        endSum[endoe] = [ends]
        endIndex[endoe] = [-i]
#print(pre)
#print(ends)
#print(endIndex)
#print(endSum)
ans = 0
for i in range(n+1):
    p = pre[i][1]
    if pre[i][0] > ans and p == 0 and pre[i][0] <= k:
        ans = pre[i][0]
    if -p in endSum:
        #print('endSum[-p]' , endSum[-p] , pre[i][0] , k - pre[i][0])
        q = bisect.bisect_left(endSum[-p], k - pre[i][0]+1)#找與pre[i][0](前綴)相加小於k的資料位置
        if q > 0:
            #print(pre[i][0] , endSum[-p][q-1])
            q = bisect.bisect_left(endIndex[-p][0:q],-i)#找到所有相加符合標準中，起始位置最左邊的後綴合(後綴起始位置越左邊越大)
            if q > 0:
                #print(q)
                ans = max(ans , pre[i][0] + endSum[-p][q-1])
                #print(ans)
        
print(ans)