CODEWITHSUNDEEP
algorithmdynamic-programming
user3840069
user3840069

Reputation: 765

Find maximum balanced subarray

Given a character parenthesis array and an integer array.

We need to find the maximum sum sub-array in the integer array such that the corresponding sub-array in the character array has balanced parenthesis. Formally, a balanced parentheses is subset of { [,],{,},<,>,(,) }∗ defined recursively as follows:

The empty string is balanced parentheses.
If A is balanced parentheses, then so are the strings [A], {A} , <A>, (A).
If A and B are balanced parenthesis, then so is the string AB.

Let N=4 and character array be : ()() and integer array be -1 -2 3 4 then answer is 7 as last 2 elements: 3 + 4 = 7.

How to find maximum sum for given character array and integer array ?

I am currently checking maximum sub array and then checking if its balanced or not and continuing it till i get balanced one. But this is inefficient. Is their any efficient way as N <=10^5

Upvotes: 2

Views: 1039

Answers (1)

amit
amit

Reputation: 178411

Using a push down automaton, you can create find all the places where he parentheses are balanced. This will be a series of indices i_1,i_2,...,i_k. Assuming the array is balanced itself, i_k = n-1 (0 based indices).
The above can be done in linear time.

Using the above, you can crate an auxillary array, defined as:

aux[k] = intArray[i_(k-1) + 1] + intArray[i_(k-1) + 2] + ... + intArray[i_(k)-1] + intArray[i_k]

In words: the element k is the sum of elements from element i_(k-1) (exclusive) until i_k (inclusive). (i_0 is defined as i_0=-1 for simplifying things).

The above is an array containing all sums with corresponding balanced parentheses , and you can now invoke the "regular" maximum sum algorithm on aux, to find the answer.

The proof of correctness will be based on the fact that each set of balanced parentheses (including the optimal one) is a candidate to the max subarray algorithm, and every subarray in aux is a balanced parentheses series.

pseudo code:
Assuming existence of findMaxSubArray(arr) that returns "regular" maximum sub array algorithm:

stack s = new Stack()
cands= new list
cands.add(-1)
for (int i = 0; i < parantheses.length; i++)
   if parantheses[i] == '(' ||  parantheses[i] == '[' || parantheses[i] == '{':
       stack.push(parantheses[i]) 
       continue
   if stack.peek() == '(' && parantheses[i] == ')':
       stack.pop() //remove head of stack
   else if stack.peek() == '[' && parantheses[i] == ']':
      stack.pop()
   //similar line for '}'
   if stack.isEmpty(): //found balanced subarray
        cands.add(i)
//at this point we have a list cands containing ends of all valid parantheses.
//we now wish to make aux of the corresponding sums
int[] aux = new int[cands.length - 1];
for (int i = 1; i<aux.length; i++)
     start = cands.get(i-1)
     end = cands.get(i)
     aux[i-1] = 0
     for (int j = start+1; j<= end; j++):
        aux[i-1] += intsArray[j];
     //when done, aux[i-1] is the sum of balances parantheses cands_{i-1} until cands_i
//we have established our aux array
return findMaxSubArray(aux)

Upvotes: 2

Related Questions