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     }