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.
. should have declared outside