最长有效括号

//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"

public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

动态规划

public int longestValidParentheses(String s) {
        if(s==null || s.length()<=1){
            return 0;
        }
        char[] chars = s.toCharArray();
        int [] dp=new int[chars.length];
        dp[0]=0;
        int max=Integer.MIN_VALUE;
        for (int i = 1; i < chars.length; i++) {
            if(chars[i]=='('){
                dp[i]=0;
            }else{
                if(chars[i-1]=='('){
                    if(i-2>=0){
                        dp[i]=dp[i-2]+2;
                    }else{
                        dp[i]=2;
                    }

                }else{
                    if(i-dp[i-1]-1>=0&&chars[i-dp[i-1]-1]=='('){
                        dp[i]=dp[i-1]+2;
                        if(i-dp[i-1]-2>=0){
                            dp[i]=dp[i]+dp[i-dp[i-1]-2];
                        }
                    }
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }