Python [DP on subsequences]
Let dp(sub) be a DP that finds longest palindromic subsequence on a given string sub. Caching intermediate results, this is done in linear time.\n\nWe need to s
Let `dp(sub)` be a DP that finds longest palindromic subsequence on a given string `sub`. Caching intermediate results, this is done in linear time.\n\nWe need to split into all possible subsets, on top of which we can apply DP. There are `2**12 = 4096` such splits at most, so we can cache the substrings.\n\nWe find the substrings using bitmask.\nGo only half length as the remaining is covered by symmetry. This cuts runtime in half.\n\n```python\nclass Solution:\n    def maxProduct(self, s):\n        @lru_cache(None)\n        def dp(sub):\n            if not sub:\n                return 0\n            if len(sub) == 1:\n                return 1\n            if len(sub) == 2:\n                return 2 if sub[0] == sub[1] else 1\n            if sub[0] == sub[-1]:\n                return 2 + dp(sub[1:-1])\n            return max(dp(sub[1:]), dp(sub[:-1]))\n        \n        ans = 0\n        for mask in range(2**len(s) // 2):\n            sub1 = \'\'\n            sub2 = \'\'\n            for j in range(len(s)):\n                if (mask >> j) & 1:\n                    sub1 += s[j]\n                else:\n                    sub2 += s[j]\n            ans = max(ans, dp(sub1) * dp(sub2))\n        return ans\n```
[]