題：
給定一個整數陣列 A 和分數 S = 0。對于陣列中的每個位置，您可以執行以下操作之一：
- 放置一個“（”。分數將是 S = Ai
- 放置一個“）”。分數將是 S -= Ai
- 跳過它
為了使括號平衡，您可以獲得的最高分是多少？
限制：
- |艾| <= 10^9
- 陣列 A 的大小：<= 10^5
附：
我嘗試了很多方法，但我最好的方法是使用 O(3^n) 的蠻力。有沒有辦法在 O(n.logn) 或更少的時間內解決這個問題？
uj5u.com熱心網友回復：
您可以O(n log n)使用最大堆及時完成此操作。
首先，消除操作中的不對稱性。假設我們從 的運行總和開始-sum(A)，即所有閉括號，而不是有開括號和閉括號。現在，對于 A 中的每個元素，我們可以將它添加到我們的運行總和中零次、一次或兩次，分別對應于離開一個封閉的括號、移除封閉的括號或添加一個開放的括號。平衡約束現在說在處理第一個k元素之后，我們有：
k對所有整數進行至少加法k，- 我們進行
length(A)總添加。 - 我們已將最后一個元素添加到我們的總和中零次或一次。
假設在處理了第一個k元素之后，我們進行了k添加，并且我們擁有所有此類配置中可能的最高分。我們可以貪婪地將其擴展到k 1帶有k 1添加的第一個元素的最大分數配置。我們有一個新的選擇，將k 1-th元素添加到我們的總和中最多兩次，但現在最多只能添加一次。只需選擇兩次尚未添加到我們的總和中的最大可見元素，并將其添加到我們的總和中：這也必須是最大分數配置，否則我們可以顯示舊配置也不是最大值。
Python 代碼：（所有值都被否定，因為 Python 只有一個最小堆）
def solve(nums: List[int]) -> int:
"""Given an array of integers, return the maximum sum achievable.
We must add k elements from nums and subtract k elements from nums,
left to right and all distinct, so that at no point have we subtracted
more elements than we have added.
"""
max_heap = []
running_sum = 0
# Balance will be 0 after all loop iterations.
for value in nums:
running_sum -= value # Assume value is subtracted
heapq.heappush(max_heap, -value) # Option to not subtract value
heapq.heappush(max_heap, -value) # Option to add value
# Either un-subtract or add the largest previous free element
running_sum -= heapq.heappop(max_heap)
return running_sum
uj5u.com熱心網友回復：
您可以使用二維陣列highest_score在O ( n 2 ) 時間內完成此操作，其中highest_score [ i ][ b ] 是位置i之后可達到的最高分數，其中b方括號尚未關閉。每個元素highest_score [ i ][ b ] 僅取決于highest_score [ i ?1][ b ?1] 、highest_score [ i ?1][ b ] 和highest_score [ i ?1][ b ] 1]（當然還有A [ i ]），所以每一行highest_score [ i ] 可以在O ( n ) 時間內從前一行highest_score [ i ?1] 計算出來，最終的答案是highest_score [ n ][ 0]。
（注意：這使用了O ( n 2 ) 空間，但由于highest_score 的每一行僅取決于前一行，您實際上可以通過重用行在O ( n ) 中完成。但是漸近運行時復雜度將是相同的.)
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369676.html
上一篇：雙向鏈表的歸并排序
下一篇：在網格中找到第K個最小元素？