PROBLEM LINK:Author: Devendra Agarwal 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 subarray in the integer array such that the corresponding subarray 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: 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: 1) Declare a character stack $S$.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”. Original Problem: for(int i=0;i<=N+1;i++) hsh[i] = 0; // This array will store j for each i. stack<int> 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 $i1$, 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 subarray valid, if its corresponding character array is balanced. Let dp[i] denotes maximum sum valid subarray 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))$ 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 subarray we can iterate over each $i$ and take maximum of $DP[i]$. Solutions:Setter's solution can be found here.
This question is marked "community wiki".
asked 10 Feb '15, 01:52

can anybody tell why this solution got tle solution answered 16 Feb '15, 00:30
@Anurag92, You are declaring sum[100100] in each of the test case. While there can be 10^5 test cases. You should either keep it global or declare array of size N.
(16 Feb '15, 00:33)
thnx :) . should have declared outside
(16 Feb '15, 00:42)

j=i1 or (flagvalue,say:1) I don't think j can take any other value according to you.Am I correct? If we take j as the smallest j such that [j,i] is valid, then sum of elements from j,i should be the answer and that can be calculated in O(1) by keeping prefix sums array.Is this solution Correct? answered 20 Feb '15, 03:17
@saurv4u, take $j$ as the largest value such that $[j,i]$ is valid. In this way, you will be able to use dynamic programming approach.
(20 Feb '15, 10:40)

Used the exact same logic but got WA. If I find a closing bracket which does not match with the top most bracket in the stack, do I need to push it in the stack? I don't think it should make any difference. And can I know for which test cases did my code fail? answered 22 Feb '15, 02:23

I think you should note that \text{DP[i]} is initialized to 0 in the recurrence and the recurrence is only defined for \text{i} such that there is a balanced expression ending at \text{i}. Also, you never mention that \text{sum(hsh[i], i)} is the sum of the array from \text{hsh[i]} to \text{i}.
Anyway, thank you for the editorial! When I first saw this problem in the CookOff, I thought it was really hard, but now I see it wasn't that bad after all!