Problem:
Given a string containing just the characters'(‘and’)’, find the length of the longest valid (well-formed) parentheses substring.
For"(()", the longest valid parentheses substring is"()", which has length = 2.
Another example is")()())", where the longest valid parentheses substring is"()()", which has length = 4.
Solution:
维持一个字符栈和位置栈，字符栈记录没有匹配的字符，位置栈记录每一个入栈的字符的位置，如果入栈的是右括号，并且栈顶为左括号，则退栈，求出当前连续退栈的字符长度，求出这个最大值就是。
题目大意：
给一个字符串，只包含左括号和右括号，，求出这个字符串合法括号的最大长度。
Java源代码（350ms）：
public class Solution {public int longestValidParentheses(String s) {int len=s.length(),max=0;Stack<Character> str_stack = new Stack<Character>();Stack<Integer> pos_stack = new Stack<Integer>();char[] str=s.toCharArray();for(int i=0;i<len;i++){if(str[i]=='('){str_stack.push('(');pos_stack.push(i);}else{if(str_stack.size()>0 && str_stack.peek().equals('(')){str_stack.pop();pos_stack.pop();int tmp=pos_stack.size()==0?i+1:i-pos_stack.peek();max=Math.max(max,tmp);}else{str_stack.push(')');pos_stack.push(i);}}}return max;}}C语言源代码（3ms）：
int longestValidParentheses(char* s) {int len=strlen(s),max=0,top=0,i,tmp;int* pos_stack=(int*)malloc(sizeof(int)*len);char* str_stack=(char*)malloc(sizeof(char)*len);for(i=0;s[i];i++){if(s[i]=='('){str_stack[top]='(';pos_stack[top]=i;top++;}else{if(str_stack[top-1]=='('){top–;if(top==0)tmp=i+1;else tmp=i-pos_stack[top-1];max=max>tmp?max:tmp;}else{str_stack[top]=')';pos_stack[top]=i;top++;}}}return max;}C++源代码（7ms）：
class Solution {public:int longestValidParentheses(string s) {int max=0,top=0,len=s.size();int* pos_stack=(int*)malloc(sizeof(int)*len);char* str_stack=(char*)malloc(sizeof(char)*len);for(int i=0;i<len;i++){if(s[i]=='('){str_stack[top]='(';pos_stack[top]=i;top++;}else{if(str_stack[top-1]=='('){int tmp;top–;if(top==0)tmp=i+1;else tmp=i-pos_stack[top-1];max=max>tmp?max:tmp;}else{str_stack[top]=')';pos_stack[top]=i;top++;}}}return max;}};Python源代码（105ms）：
class Solution:# @param {string} s# @return {integer}def longestValidParentheses(self, s):length=len(s);top=0;Max=0str_stack=[' ' for i in range(length)]pos_stack=[0 for i in range(length)]for i in range(length):if s[i]=='(':str_stack[top]='('pos_stack[top]=itop+=1else:if top>0 and str_stack[top-1]=='(':top-=1tmp=i+1 if top==0 else i-pos_stack[top-1]Max=Max if Max>tmp else tmpelse:str_stack[top]=')'pos_stack[top]=itop+=1return Max
“但行好事，莫问前程”，往往成功的几率反而更大些;
