032.md

32. Longest Valid Parentheses

Solution 1 (O(n))

// Dynamic programming
class Solution {
    public int longestValidParentheses(String s) {
        int length = s.length();
        if (length == 0)
            return 0;
        int ans[] = new int[length];
        ans[0] = 0;
        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == ')') {
                int j = i - 1 - ans[i - 1];
                if (j >= 0 && s.charAt(j) == '(') {
                    ans[i] = ans[i - 1] + 2;
                    if (j - 1 >= 0) {
                        ans[i] += ans[j - 1];
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < length; i++)
            if (ans[i] > ret)
                ret = ans[i];
        return ret;
    }
}