最长的有效括号

题目描述：
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度.

示例：
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

Java代码：

class Solution {
    1、First of All，栈底永远保存着当前有效子串的前一个字符的下标，就像个守门员一样守在那里，
       所以一开始要将-1放入栈中。
    2、遇到左括号就入栈；
    3、遇到右括号就将栈顶元素出栈。此时有两种情况：
   （1）如果栈顶元素出栈后，栈内剩下的元素不为空，则说明弹出的这个栈顶元素一定是左括号，
       因为栈底有保险。
   （2）如果栈顶元素出栈后，栈内为空，则说明刚刚弹出的这个栈顶元素就是之前的“有效子串前一位的字符下标”，
       守门员都没了，所以此时应该使用当前的右括号的下标入栈，更新这个“有效子串前一位的字符下标”。
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int maxans = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        dq.push(-1);

        for(int i = 0;i < s.length();i++) {
            if(s.charAt(i) == '(') {
                dq.push(i);
            } else {
                dq.pop();
                if(dq.isEmpty()) {
                    dq.push(i);
                } else {
                    maxans = Math.max(maxans, i - dq.peek());
                }
            }
        }
        return maxans;
    }
    //动态规划
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int maxans = 0;
        
        int dp[] = new int[s.length()];
        for(int i = 1;i < s.length();i++) {
            if(s.charAt(i) == ')') {
                if(s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}