SUBARRAY - Editorial

cook55
data-structure
dynamic-programming
medium
subarray

#1

PROBLEM LINK:

Practice
Contest

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.

  1. Declare a character stack S.
  2. 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.
  1. 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* = 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*) && s[st.top()] == opposite(s*)) {
			hsh* = 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* denotes maximum sum valid sub-array
ending at position i.
So recurrence for DP will be as follows.

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


hsh* ext{ is the largest j (j < i) such that segment} [j,i] ext{ 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*.

Solutions:

Setter’s solution can be found here.

Tester’s solution can be found here.


#2

can anybody tell why this solution got tle
solution


#3

why largest index j in the hsh[] array?


#4

shouldn’t it be for all j < i such that [j, i] is properly parenthesized?


#5

For each i, there will be only one j such that [j,i] will be balanced. I couldn’t come up with a counter example, so I assume its true.


#6

can anybody tell why this solution got wa link text


#7

I applied the same logic, but got tle. Can anybody suggest what’s wrong in my solution


#8

j=i-1 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?


#9

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?

http://www.codechef.com/viewsolution/6329799


#10

Some test cases would be appreciated. I get ‘Wrong Answer’, but not sure for which cases.
Not even sure if I’m reading the data incorrectly or just algorithm is wrong.
Can somebody throw in a few ‘tricky’ test cases?


#11

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


#12

thnx :slight_smile: . should have declared outside


#13

Sorry for the confusion, please check now.


#14

Actually i’m wondering why not for all j < i such that [j, i] is properly parenthesized?


#15

correct me if i’m mistaken anywhere :slight_smile:


#16

according to the solution, you are trying to keep [j,i] segment length as minimum as possible


#17

Didn’t get you, please elaborate.


#18

will there be a unique j for each i? Actually i tried making a balanced parenthesis but observed that j is always unique. if i tried making j lesser ( close to index 0 ), the segment [j,i] was getting imbalanced. I’ll figure out my confusion. Thanks :slight_smile:


#19

Yes, I am talkign about largest j, such that segment [j,i] is balanced.


#20

Just try to realize it using the fact which is written in penultimate line.