问题描述
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.
问题分析： 题目要求计算最长合法括号的子串长度。括号匹配问题首先想到的是利用栈，利用start记录合法括号开始的位置，遇到左括号将下标入栈；遇到右括号出栈，如果当前栈为空，更新长度为i-start+1，如果栈不为空，更新长度为i-stack.top() 代码如下：
public int longestValidParentheses(String s) { if(s==null||s.length()==0) return 0; int n=s.length(); int max=0; int start=0; LinkedList<Integer> stack=new LinkedList<Integer>(); for(int i=0;i<n;i++){ if(s.charAt(i)=='(')//左括号入栈 stack.addFirst(i); else//右括号 { if(stack.size()==0)//不存在与之匹配的左括号 { start=i+1;//更新下一个合法左括号位置 } else//存在与之匹配的左括号 { stack.removeFirst(); if(stack.size()==0) max=Math.max(max,i-start+1); else max=Math.max(max,i-stack.get(0)); } } } return max; }另一个利用动态规划的方法：从右向左计算当前左括号为合法子串的最右边左括号时子串长度，所以有状态转移矩阵： if（s[j]==’)’) dp[i]=dp[i+1]+2//括号内部，dp[i]+=dp[j+1];//括号右边, (j=i+dp[i+1]+1,并且需要判断边界) 代码如下：
public int longestValidParentheses(String s) { if(s==null||s.length()==0) return 0; int n=s.length(); int[]dp=new int[n]; int max=0; for(int i=n-2;i>=0;i--){ if(s.charAt(i)=='('){ int j=i+dp[i+1]+1; if(j<n&&s.charAt(j)==')')//i括号中间的括号 { dp[i]=dp[i+1]+2; if(j+1<n)//i括号右边的完整括号 dp[i]+=dp[j+1]; } if(max<dp[i]) max=dp[i]; } } return max; }