1. 题目：
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.
2. 思路
初始思路
从字符串中每个位置开始，求以该位置开始的最长合法字串长度，然后从这些字串中选出最长的。时间复杂度O(n^2)
改进
可以利用前面已经产生的结果，减少匹配不必要的匹配
1 class Solution { 2 public int longestValidParentheses(String s) { 3 int[] records = new int[s.length()]; 4 int max = 0; 5 for (int i = 1; i < s.length(); i++) { 6 boolean match = false; 7 if ( s.charAt(i) == ‘)‘) { 8 if (s.charAt(i-1) == ‘(‘) { 9 records[i] = 2; 10 match = true; 11 } 12 else if (records[i-1] > 0 && i - records[i-1] > 0 && s.charAt(i - records[i-1] - 1) == ‘(‘) { 13 records[i] = records[i - 1] + 2; 14 match = true; 15 } 16 if (match) { 17 if (i - records[i] >= 0 && records[i - records[i]] > 0) { 18 records[i] += records[i - records[i]]; 19 } 20 max = max > records[i] ? max : records[i]; 21 } 22 } 23 } 24 return max; 25 } 26 }
LeetCode:32 Longest Valid Parentheses
原文：http://www.cnblogs.com/hungry-bird/p/7867339.html