O(n) DP solution in C++
  \n       int longestValidParentheses(string s) {\n            int cnt = 0; // count of "("\n            vector<int> dp(s.size()+1, 0);\n            \n        
      \n       int longestValidParentheses(string s) {\n            int cnt = 0; // count of "("\n            vector<int> dp(s.size()+1, 0);\n            \n            for (size_t i = 1; i <= s.size(); i++) {\n                if (s[i-1] == '(') {\n                    cnt++;\n                } else {\n                    if (cnt > 0) {  // there exists an unclosed "(" to match ")"\n                        cnt--;\n                        dp[i] = 2;\n                        if (s[i-2] == ')')  // add the length of previous closed ")" neighbor\n                            dp[i] += dp[i-1];                        \n                        dp[i] += dp[i-dp[i]]; // add the length of previous valid parentheses\n                    }\n                }\n            }\n            \n            return *max_element(dp.begin(), dp.end());\n        }
['C++']