Maximum Product of the Length of Two Palindromic Subsequences LeetCode solution in C++

1
class Solution {
2
 public:
3
  int lca(string &s) {
4
    int n = s.size();
5
    string s1 = s;
6
    string s2 = s;
7
    reverse(s2.begin(), s2.end());
8
    int dp[s.size() + 1][s.size() + 1];
9
    memset(dp, 0, sizeof(dp));
10
    for (int i = 1; i <= n; i++) {
11
      for (int j = 1; j <= n; j++) {
12
        dp[i][j] =
13
            (s1[i - 1] == s2[j - 1]) ? 1 + dp[i - 1][j - 1] : max(dp[i][j - 1], dp[i - 1][j]);
14
      }
15
    }
16
    return dp[n][n];
17
  }
18
  int maxProduct(string s) {
19
    int ans = 0;
20
    int n = s.size();
21
    for (int i = 1; i < (1 << n) - 1; i++) {
22
      string s1 = "", s2 = "";
23
      for (int j = 0; j < n; j++) {
24
        if (i & (1 << j)) {
25
          s1.push_back(s[j]);
26
        } else {
27
          s2.push_back(s[j]);
28
        }
29
      }
30
      ans = max(ans, lca(s1) * lca(s2));
31
    }
32
    return ans;
33
  }
34
};