正向逆向结合法

思路：

1、定义三个变量：

1. leftNum : 表示左括号的数量
2. rightNum： 表示右括号的数量
3. maxLen：表示合法括号的最大长度

2、正向遍历

从左往右遍历一次原始括号字符串:

1. 如果碰到左括号：'('，则 leftNum++;
2. 如果碰到右括号：')'，则 rightNum++;
3. 如果左右括号数目相等，那么说明此时是一个合法的括号子串，就要更新最大长度：max(maxLen, leftNum + rightNum);
4. 如果右边的括号数量大于左边的括号数量，也就是rightNum > leftNum, 则说明括号非法，说明此时这个')'加进来后，使得括号子串非法，那么此时也就是说明加进来的这个')' 将前面的合法括号子串和后面的进行了一个分割，所以此时就需要重置左右括号数量为0；例如：
   

3、逆向遍历

从右往左遍历一次原始括号字符串

1. 如果碰到左括号：'('，则 leftNum++;

2. 如果碰到右括号：')'，则 rightNum++;

3. 如果左右括号数目相等，那么说明此时是一个合法的括号子串，就要更新最大长度：max(maxLen, leftNum + rightNum);

4. 如果左边的括号数量大于右边的括号数量，也就是 leftNum > rightNum , 则说明括号非法，说明此时这个'('加进来后，使得括号子串非法，那么此时也就是说明加进来的这个'(' 将前面的合法括号子串和后面的进行了一个分割，所以此时就需要重置左右括号数量为0；(此处逻辑和第二步类似)

   思考：那么为什么要逆向遍历一次？

   请看如下情况：
   当出现第②种情况的时候，会出现左右括号数量不一致的情况，那么可以再次进行一次逆向遍历，然后求出长度，更新长度，才是最终的长度；
   

   代码：

   import java.util.*;
   public class Solution {
    /**
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        if(s == null || s == ""){
            return 0;
        }
        int len = s.length();
        int leftNum = 0;
        int rightNum = 0;
        int maxLen = 0;
        // 左 --> 右
        for(int i = 0; i<len; i++){
            char c = s.charAt(i);
            if(c == '('){
                leftNum++;
            }else{
                rightNum++;
            }
            if(leftNum == rightNum){
                maxLen = Math.max(maxLen, leftNum + rightNum);
            }else if(rightNum > leftNum){
                leftNum = 0;
                rightNum = 0;
            }
        }
   
        // 从右到左
        leftNum = 0;
        rightNum = 0;
        for(int i = len-1; i>=0; i--){
            char c = s.charAt(i);
            if(c == '('){
                leftNum++;
            }else{
                rightNum++;
            }
            if(leftNum == rightNum){
                maxLen = Math.max(maxLen, leftNum + rightNum);
            }else if(rightNum < leftNum){
                leftNum = 0;
                rightNum = 0;
            }
        }
        return maxLen;
    }
   }