制作得分最高的平衡支架

Question

问题：

给定一个整数数组 A 和一个分数 S = 0。对于数组中的每个位置，您可以执行以下操作之一：

放置一个“(”。得分为S += Ai
放置一个“)”。分数将是 S -= Ai
跳过

你能得到多少分才能使括号平衡？

限制：

|艾| <= 10^9
数组 A 的大小：<= 10^5

P/S:

我已经尝试了很多方法，但我最好的方法是使用 O(3^n) 的蛮力。有没有办法在 O(n.logn) 或更短的时间内解决这个问题？

Answer 1

您可以在 O(n²) 时间内使用两个维数组highest_score，其中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²) space , 但由于 highest_score 的每一行只依赖于前一行，你实际上可以在 O(n) 通过重用行。但是渐近运行时复杂度将是相同的两种方式。)

Answer 2

使用最大堆，您可以在 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

制作得分最高的平衡支架

Make balance bracket with highest score

algorithm

brackets

dynamic-programming