Maximum Product of the Length of Two Palindromic Subsequences | C++ | LPS
LPS : Longest Palindromic Subsequence\n\nclass Solution {\npublic:\n    int LPS(string& s1) {\n        string s2 = s1;\n        reverse(s2.begin(), s2.end());\n
LPS : Longest Palindromic Subsequence\n```\nclass Solution {\npublic:\n    int LPS(string& s1) {\n        string s2 = s1;\n        reverse(s2.begin(), s2.end());\n        \n        int n = s1.size();\n        int dp[n + 1][n + 1];\n        for(int i = 0; i < n; i++) dp[i][0] = 0, dp[0][i] = 0;\n        \n        for(int i = 1; i <= n; i++){\n            for(int j = 1; j <= n; j++){\n                if(s1[i - 1] == s2[j - 1]){\n                    dp[i][j] = 1 + dp[i - 1][j - 1];\n                }\n                else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);\n            }\n        }\n        return dp[n][n];\n    }\n\n    int maxProduct(string s) {\n        int ans = 0, n = s.size();\n        for(int mask = 1; mask < (1 << n) - 1; mask++){\n            string a = "", b = "";\n            for(int i = 0; i < n; i++){\n                if(mask & (1 << i)) a += s[i];\n                else b += s[i];\n            }\n            ans = max(ans, LPS(a) * LPS(b));\n        }\n        return ans;\n    }\n};\n```
[]