C++ solution | Little tricky O(n)
\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n=s.length();\n        vector<int>dp(n+1,0);\n        stack<int>st;\n     
```\nclass Solution {\npublic:\n    int longestValidParentheses(string s) {\n        int n=s.length();\n        vector<int>dp(n+1,0);\n        stack<int>st;\n        int ans=0;\n        int temp=0;\n        for(int i=0;i<n;i++)\n        {\n            if(s[i]==\'(\')\n                st.push(i);\n            else\n            {\n                if(!st.empty())\n                {\n                    int k=st.top();\n                    st.pop();\n                    dp[k]=(i-k+1);\n                }\n            }\n        }\n        int i=0;\n        while(i<n)\n        {\n            if(dp[i]==0)\n            {\n                temp=0;\n                i++;\n            }\n            else\n            {\n                temp+=dp[i];\n                i+=dp[i];\n            }\n            ans=max(ans,temp);\n        }\n        ans=max(ans,temp);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Stack', 'C', 'C++']