Recursive c++ solution with memoization . O(n)
/\nT : O(n)\nS : O(n)\nIdea : try to break in smaller sub problem .\ncase 1: string ends at "()"\nlongestParenEnding(0, i) = longestParenEnding(0, i - 2) + 2\n\
/*\nT : O(n)\nS : O(n)\nIdea : try to break in smaller sub problem .\ncase 1: string ends at "()"\nlongestParenEnding(0, i) = longestParenEnding(0, i - 2) + 2\n\ncase 2: string ends with "))" for example "()(())"\nlongestParenEnding(0, i) = \n\ncase 3: string ends with "("\nlongestParenEnding(0, i) = 0\n*/\n```\nclass Solution {\n    int lonParen(int i, string & s, vector<int> & memo){\n        if(i <= 0){\n            return 0;\n        }\n        \n        if(memo[i] != -1){\n            return memo[i];\n        }\n        \n        if(s[i] == \'(\'){\n            memo[i] = 0;\n        }\n        else if(s[i] == \')\' && s[i - 1] == \'(\'){\n            memo[i] = lonParen(i - 2, s, memo) + 2;\n        }\n        else if(s[i] == \')\' && s[i - 1] == \')\'){\n            int len = lonParen(i - 1, s, memo);\n            if(i - 1 - len >= 0 && s[i - 1 - len] == \'(\'){\n                memo[i] = len + 2 + lonParen(i - len - 2, s, memo);\n            }\n            else{\n                memo[i] = 0;\n            }\n        }\n        return memo[i];\n    }\npublic:\n    int longestValidParentheses(string s) {\n        \n        int n = s.size(), maxLen = 0;\n        vector<int> memo(n, -1);\n        for(int i = 0; i < n; i++){\n            maxLen = max(maxLen, lonParen(i, s, memo));\n        }\n        return maxLen;\n    }\n};\n```
['Recursion', 'Memoization', 'C++']