Longest Valid Parentheses

Longest Valid Parentheses

 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.

------------------------------ thinking --------------------------------------------------
BUG -> remember to update the valid starting top of local parentheses substring
https://oj.leetcode.com/discuss/21549/simple-java-solution-o-n-time-one-stack
https://oj.leetcode.com/discuss/21880/people-conclusion-cannot-done-with-space-solution-time-space
https://oj.leetcode.com/discuss/19067/o-n-one-pass-solution-without-stacks
------------------------------- codes ----------------------------------------------------
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int max = 0;
        //bug here -> the braking top needs to be updated all the time -> e.g. ")()())()()("
        int brake_top = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                if (stk.size() != 0) {
                    stk.pop();
                    //bug here -> use the right local top value to find the correct local valid length
                    int top = brake_top;
                    if (stk.size() != 0) {
                        top = stk.top();
                    }
                    int length = i - top;
                    if (length > max) {
                        max = length;
                    }
                } else {
                    brake_top = i;
                }
            }
        }
        return max;
    }
};