@@ -0,0 +1,1668 @@
+/***%0A * Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.%0A *%0A * For %22(()%22, the longest valid parentheses substring is %22()%22, which has length = 2.%0A *%0A * Another example is %22)()())%22, where the longest valid parentheses substring is %22()()%22, which has length = 4.%0A */%0Apublic class Solution %7B%0A    // Solution 1: O(n)%0A    /*%0A    public int longestValidParentheses(String s) %7B%0A        int n = s.length();%0A        Stack%3CInteger%3E stk = new Stack%3CInteger%3E();%0A        int max_len = 0, last = -1;%0A%0A        for (int i = 0; i %3C n; i++) %7B%0A            if (s.charAt(i) == '(') %7B%0A                stk.push(i);    // store positions of '('%0A                continue;%0A            %7D%0A%0A            if (stk.isEmpty()) %7B%0A                last = i;%0A                continue;%0A            %7D%0A%0A            stk.pop();%0A            if (stk.isEmpty())%0A                max_len = Math.max(max_len, i - last);%0A            else%0A                max_len = Math.max(max_len, i - stk.peek());%0A        %7D%0A        return max_len;%0A    %7D%0A    */%0A%0A    // Solution 2. Dynamic Programming O(n)%0A    public int longestValidParentheses(String s) %7B%0A        int n = s.length();%0A        int f%5B%5D = new int %5Bn%5D;%0A        int ret = 0;%0A        for (int i = n - 2; i %3E= 0; --i) %7B%0A            int match = i + f%5Bi + 1%5D + 1;%0A            // case %22(( ... ))%22%0A            if (s.charAt(i) == '(' && match %3C n && s.charAt(match) == ')') %7B%0A                f%5Bi%5D = f%5Bi + 1%5D + 2;%0A                // case %22((...))()%22%0A                if (match + 1 %3C n) f%5Bi%5D +=f%5Bmatch + 1%5D;%0A            %7D%0A            ret = Math.max(ret, f%5Bi%5D);%0A        %7D%0A        return ret;%0A    %7D%0A%7D%0A

add LongestValidParentheses.java