Share my java solution with stack and DP
Stack:\n    \n        public int longestValidParentheses(String s) {\n            Stack st = new Stack<>();\n            int max = 0;\n            for(int i=0;i
Stack:\n    \n        public int longestValidParentheses(String s) {\n            Stack<Integer> st = new Stack<>();\n            int max = 0;\n            for(int i=0;i<s.length();i++){\n                if(s.charAt(i)==')'&&!st.isEmpty()&&s.charAt(st.peek())=='('){\n                    st.pop();\n                    max = Math.max(max, i-((st.isEmpty())?-1:st.peek()));\n                }\n                else    st.push(i);\n            }\n            return max;\n        }\n\nDP:\n\n    public int longestValidParentheses(String s) {\n        /*max[i] = j means subsequence index i-j is longest valid Parentheses*/\n        int[] max = new int[s.length()+1];\n        max[s.length()] = s.length();\n        int sum = 0;\n        for(int i=s.length()-1;i>=0;i--){\n            if(max[i+1]!=i+1){\n                if(max[i+1]+1<s.length()&&s.charAt(i)=='('&&s.charAt(max[i+1]+1)==')'){\n                    max[i] = (max[i+1]+2<s.length()+1&&max[max[i+1]+2]!=max[i+1]+2)?max[max[i+1]+2]:max[i+1]+1;\n                }\n                else    max[i] = i;\n            }\n            else if(i+1<s.length()&&s.charAt(i+1)==')'&&s.charAt(i)=='('){\n                max[i] = (i+2<s.length()+1&&max[i+2]!=i+2)?max[i+2]:i+1;\n            }\n            else    max[i] = i;\n            sum = Math.max(sum, max[i]-i+1);\n        }\n        return (sum==1)?0:sum;\n    }
['Stack']