Longest Valid Parentheses

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

C++:
01 int longestValidParentheses(string s)
02 {
03     stack<int> tmp;
04     int n=s.size();
05     int max=0;
06     int prv=n;
07     for(int i=0;i<n;i++){
08         if(s[i]==‘(‘){
09              if(prv==n)
10                  tmp.push(i);
11              else
12                  tmp.push(prv);
13              prv=n;
14         }
15         else if(s[i]==‘)’){
16              if(tmp.empty()){
17                   prv=n;
18              }
19              else{
20                  int j=tmp.top();
21                  tmp.pop();
22                  prv=j;
23                  if(iprv+1>max)
24                      max=iprv+1;
25              }
26        }
27     }
28     return max;
29 }
Advertisements
This entry was posted in Array and linked list, Stack and Queue, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s