You are not logged in. Please login at www.codechef.com to post your questions!

×

SUBARRAY - Editorial

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

3) 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<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 $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.

This question is marked "community wiki".

asked 10 Feb '15, 01:52

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 19:13

admin's gravatar image

0★admin ♦♦
19.8k350498541

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 Cook-Off, I thought it was really hard, but now I see it wasn't that bad after all!

(20 Feb '15, 20:30) noble_mushtak5★

can anybody tell why this solution got tle solution

link

answered 16 Feb '15, 00:30

anurag92's gravatar image

2★anurag92
114
accept rate: 0%

@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) amitpandeykgp4★

thnx :) . should have declared outside

(16 Feb '15, 00:42) anurag922★

why largest index j in the hsh[] array?

link

answered 16 Feb '15, 00:42

codejagger's gravatar image

2★codejagger
12
accept rate: 0%

Sorry for the confusion, please check now.

(16 Feb '15, 00:47) amitpandeykgp4★

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

(16 Feb '15, 00:52) codejagger2★

correct me if i'm mistaken anywhere :)

(16 Feb '15, 00:52) codejagger2★

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

(16 Feb '15, 00:54) codejagger2★

Yes and segment [j,i] is balanced as well.

(16 Feb '15, 13:01) amitpandeykgp4★

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

link

answered 16 Feb '15, 00:49

codejagger's gravatar image

2★codejagger
12
accept rate: 0%

Didn't get you, please elaborate.

(16 Feb '15, 00:55) amitpandeykgp4★

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 :)

(16 Feb '15, 01:00) codejagger2★

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

(16 Feb '15, 01:15) amitpandeykgp4★

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.

link

answered 16 Feb '15, 01:05

codejagger's gravatar image

2★codejagger
12
accept rate: 0%

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

(16 Feb '15, 01:15) amitpandeykgp4★
1

Counterexample: ()(), For last parenthesis, there are two j's.

(16 Feb '15, 04:02) dpraveen ♦♦4★

can anybody tell why this solution got wa link text

link

answered 16 Feb '15, 01:23

legar's gravatar image

2★legar
1
accept rate: 0%

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

link

answered 16 Feb '15, 08:42

sourabh123's gravatar image

3★sourabh123
1
accept rate: 0%

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?

link

answered 20 Feb '15, 03:17

saurv4u's gravatar image

5★saurv4u
312
accept rate: 0%

@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) amitpandeykgp4★

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

link

answered 22 Feb '15, 02:23

prateekjjw001's gravatar image

4★prateekjjw001
462
accept rate: 10%

edited 23 Feb '15, 02:04

I will read your code and will get back to you soon. :)

(23 Feb '15, 10:57) amitpandeykgp4★

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?

link

answered 02 Feb '16, 12:18

madgod's gravatar image

0★madgod
1
accept rate: 0%

Found the algo problem. Wanted to have [O(1) + stack] extra memory, naive :) If you want some test cases, I would recommend to write a function such as this to generate all combinations of input data of size N: Btw, can only use one type of brackets for this.

char BA[] = { '{', '(', '[', '<', '>', ']', ')', '}' }; void GenSolve(int i) { if(i == N) { C[i] = '\0'; solve(); return; }

if(i == 0) { for(int k = 0; k < N; ++k) A[k] = k + 1; }

for(int b = 0; b < 8; ++b) { C[i] = BA[b]; GenSolve(i + 1); } }

(03 Feb '16, 11:52) madgod0★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,589
×2,167
×1,404
×109
×68

question asked: 10 Feb '15, 01:52

question was seen: 5,882 times

last updated: 11 Feb '16, 19:13