32. Longest Valid Parentheses - jiejackyzhang/leetcode-note GitHub Wiki

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.

解题思路为Dynamic Programming。

解题的关键是找到尽量多的'(' ')' pair。 令dp[i]表示到i的max length。 顺序扫描数组，如果是'('，则open++，记录前面的'('。（用stack存'('的index会造成超时） 如果是')'，如果前面有'('，则

dp[i] = 2 + dp[i-1] + (i-2-dp[i-1] > 0 ? dp[i-2-dp[i-1]] : 0)

dp[i]由三部分组成，一对括号，dp[i-1]，dp[i-2-dp[i-1]]（如果'('前面还有部分）。

public class Solution {
    public int longestValidParentheses(String s) {
        char[] a = s.toCharArray();
        int[] dp = new int[a.length];
        int open = 0;
        int max = 0;
        for (int i=0; i<a.length; i++) {
        	if (a[i] == '(') open++;
        	if (a[i] == ')' && open > 0) {
        		dp[i] = 2 + dp[i-1] + (i-2-dp[i-1] > 0 ? dp[i-2-dp[i-1]] : 0);
        		open--;
        	}
        	if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}