32. Longest Valid Parentheses ---------H

（Q:
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.

A:

 ---------------4th pass ----split into two round,  first find matching position of  ')' ,  and then combine them 

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> matched(n, -1);
        vector<int> stack; // stack of non matched (
        for(int i =0;i<n;i++){
            if(s[i] == '('){
                stack.push_back(i);
            }else{
                if(not stack.empty()){
                    matched[i] = stack.back();
                    stack.pop_back();
                }
            }
        }
        // find the left most match
        int res = 0;
        for(int i= 0;i<n;i++){
            if(matched[i] >=0){
                int pre = matched[i];
                if(pre-1>=0 && matched[pre-1] >=0){
                    pre = matched[pre-1];
                }
                matched[i] = pre; // this need UPDATED
                res = max(res, i - pre + 1);
            }
        }
        return res;
    }
};

直觉就是用DP算法。
把输入，从empty的情况，开始加入。来看待。
记录下来，与之匹配的left parentheses的位置。  最后，再计算总长度。


---------------------------第二遍-----------------O(n)的复杂度-----即使是（）（）的向后跳的情况，也是最多发生O(n)次------------------------
思想是： 从后向前，记录一个该点最远可以达到的距离。
以后每一个新的位置 i ，如果是‘（’  首先找到它的match位置，(可能是 i+1 ,也可能是 farestMatch[i] +1 处）   。
找到match后，再查看是否是（）（）（）这种情况， 并且加上。

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        int[] farestMatch = new int[n];
        for (int i = 0; i < n; i++)
            farestMatch[i] = -1;

        // count from back, at each potision,record farest matching position
        int maxLength = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                // if next position does NOT has its matching
                int k = i + 1;// to be next tested position
                if (farestMatch[i + 1] > 0) // if i+1 position already has it
                                            // matching
                    k = farestMatch[i + 1] + 1;
                if (k < n && s.charAt(k) == ')') {
                    farestMatch[i] = k;
                    // now add possible ()()()() loops
                    while (farestMatch[i] + 1 < n && farestMatch[farestMatch[i] + 1] > 0)
                        farestMatch[i] = farestMatch[farestMatch[i] + 1];

                    maxLength = Math.max(maxLength, farestMatch[i] - i + 1);
                }
            }
        }
        return maxLength;
    }
}

----------------------------3rd Pass-------------------------------------

这次是彻底的O（n)。  而不用那个while 循环。

思想是：  用一个数组，记录其到最左端match 的位置。
          遍历的时候，用stack，记录其前一个match的位置。  然后，每次combine前一个，即得到所有的，最长的match的长度。

public class Solution {
    public int longestValidParentheses(String s) {
        int res = 0,  n = s.length();
        int [] A = new int[n]; // remember A[i]'s furthest matching position
        Arrays.fill(A,-1);
        for(int i =1;i<n;i++){
            if(s.charAt(i) ==')'){
                int pre = i-1;
                if(A[pre] >=  0) // pre position has no match
                    pre = A[pre]-1;
                if(pre>=0 && s.charAt(pre)=='('){
                    A[i] = pre;
                    if(pre-1>=0 && A[pre-1]>=0)
                        A[i] = A[pre-1];
                    res = Math.max(res, i-A[i]+1);
                }
            }
        }
        return res;
    }
}

Mistakes:
1：  当最终计算最大长度的时候，  我随手写了个    if (mostLeftMatchPos[i] > 0 ){
但是， 应该，是    if (mostLeftMatchPos[i] >= 0 ){ 的。
哎，不知道为什么，当时能那样写。
2： 开始， 当输入  为“（））的时候，陷入了死循环。
原因是当回头看到的是  与left 没有匹配的情况的时候。  光记得 update nRightMinusLeft 去了， 忘了把j的位置再减一。
3: 当计算longest的时候， 光考虑与之前的单独match了，却没有考虑输入为 “()() ”的情况。
因此，需要在for循环里加一个while语句。



Learned:
1：  不要想着， 精简代码。  重要的，是思路清楚。  最好是（只要复杂度不变） 先解决小问题。不要想着一步到位。  做正确才是最重要的。
例如，这里，刚开始，不要想着， 直接建立leftMostMatch 而，仅仅去找leftMatch即可。
至于（）（）这种情况。我们完全可以基于leftMatch数组再计算。