DP

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        int[] dp = new int[n];

        int ans = 0;
        for (int i = 1; i < n; i++){
            char c = s.charAt(i);
            if (c == ')'){
                if (s.charAt(i - 1) == '('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                else if (i - dp[i - 1] >= 1 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = ( (i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0 )+ dp[i - 1] + 2;
                }
                ans = Math.max(ans, dp[i]);
            }
        }

        return ans;
    }
}

check out stack solution