### PROBLEM LINK:

**Author**: Devendra Agarwal

**Tester**: Anudeep Nekkanti

**Editorialist**: Amit Pandey

### DIFFICULTY:

Medium.

### PREREQUISITES:

Dynamic programming and Data Structure(stack).

### PROBLEM:

You are given a character parenthesis ( having [,],{,},<,>,(,) ) array and an integer array.

You 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.

### QUICK EXPLANATION:

The given problem can be solved using a dynamic programming approach quite similar to maximum subarray problem.

We need to take care of balanced parenthesis, which can be done using a classical approach.

### EXPLANATION:

**First Problem:**

How to solve maximum sum sub array problem using Kadane ALgorithm, which is a classical dynamic programming problem.

def max_subarray(A): max_ending_here = max_so_far = 0 for x in A: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far

**Second problem:**

Given a character parenthesis array, check if it is balanced or not.

- Declare a character stack S.
- Now traverse the expression string expression.

- If the current character is a starting bracket then push it to stack.
- If the current character is a closing bracket, then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.

- After complete traversal, if there is some starting bracket left in stack then “not balanced”.

**Original Problem:**

Now back to original problem. Traverse the character array and if there is a closing brace at position i, determine the largest index(j < i) such that [j,i] is balanced. We can this in one pass of the character array using a stack. The approach is similar to the second problem given above.

for(int i=0;i<=N+1;i++) hsh[i] = 0; // This array will store j for each i. stack st; st.push(0); for (int i = 1; i <= n; i++) { if (!st.empty()) { // check if top of stack is opposite of current parenthesis. if (closingBracket(s[i]) && s[st.top()] == opposite(s[i])) { hsh[i] = st.top(); // We found j for the i. st.pop(); } else { st.push(i); } } else { st.push(i); } }

When we are at index i, we may consider what we have solved problem upto index i-1, and we have created an array DP[ \hspace{1 mm}]. Where, DP[j] stored the maximum sum ending at index j.

Dynamic Programming recurrence:

Let us call a sub-array valid, if its corresponding character array is balanced. Let dp[i] denotes maximum sum valid sub-array

ending at position i.

So recurrence for DP will be as follows.

DP[i] = max (DP[i], dp[hsh[i] - 1] + sum(hsh[i], i))

hsh[i] \text{ is the largest j (j < i) such that segment} [j,i] \text{ is the balanced.}

The given recurrence is using the simple fact if expressions E_{1} and E_{2} are balanced, expression E_{1}E_{2} is balanced.

For finding out overall maximum sum sub-array we can iterate over each i and take maximum of DP[i].

### Solutions:

Setter’s solution can be found here.

Tester’s solution can be found here.