Java o(n) very easy to understand
public int longestValidParentheses(String s) {\n        int max=0,start=0;\n        Stack<Integer> stack=new Stack();\n        int[] a=new int[s.length()];\n   
    public int longestValidParentheses(String s) {\n        int max=0,start=0;\n        Stack<Integer> stack=new Stack();\n        int[] a=new int[s.length()];\n        char[] c=s.toCharArray();\n        for(int i=0;i<c.length;i++){\n            if(c[i]=='(') stack.push(i);\n            else if(!stack.empty()){\n                start=stack.pop();\n                a[i]=i-start+1;\n                if(start>1) a[i]+=a[start-1];\n                max=Math.max(max,a[i]);\n            }\n        }\n        return max;\n    }
[]