Question:

Given an array A of integers and a score S = 0. For each place in the array, you can do one of the following:

• Place a "(". The score would be S = Ai
• Place a ")". The score would be S -= Ai
• Skip it

What is the highest score you can get so that the brackets are balanced?

Limits:

• |Ai| <= 10^9
• Size of array A: <= 10^5

P/S:

I have tried many ways but my best take is a brute force that takes O(3^n). Is there a way to do this problem in O(n.logn) or less?

CodePudding user response：

You can do this in O(n²) time by using a two-dimensional array highest_score, where highest_score[i][b] is the highest score achievable after position i with b open brackets yet to be closed. Each element highest_score[i][b] depends only on highest_score[i−1][b−1] and highest_score[i−1][b 1] (and of course A[i]), so each row highest_score[i] can be computed in O(n) time from the previous row highest_score[i−1], and the final answer is highest_score[n][0].

(Note: that uses O(n²) space, but since each row of highest_score depends only on the previous row, you can actually do it in O(n) by reusing rows. But the asymptotic runtime complexity will be the same either way.)

CodePudding user response：

You can do this in O(n log n) time with a max-heap.

First, remove the asymmetry in the operations. Rather than having open and closed brackets, assume we start off with a running sum of -sum(A), i.e. all closed brackets. Now, for every element in A, we can add it to our running sum either zero, one or two times, corresponding to leaving a closed bracket, removing the closed bracket, or adding an open bracket, respectively. The balance constraint now says that after processing the first k elements, we have:

1. Made at least k additions, for all integers k,
2. We make length(A) total additions.
3. We have added the final element to our sum either zero or one times.

Suppose that after processing the first k elements, we have made k additions, and that we have the maximum score possible of all such configurations. We can extend this to a maximum score configuration of the first k 1 elements with k 1 additions, greedily. We have a new choice going forward of adding the k 1-th element to our sum up to two times, but can only add it at most once now. Simply choose the largest seen element that has not yet been added to our sum two times, and add it to our sum: this must also be a maximum-score configuration, or we can show the old configuration wasn't maximum either.

Python Code: (All values are negated because Python only has a min-heap)

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