Concept
- Brute force
看到 length < 12
- Dynamic Programming
- Bitmask
Steps
參考自votrubac
先將所有可能的sequence 以 1~4096表示 (因為字串最長到12)
並檢查是否其為回文
是的話 dp[i] = 回文長度
否的話 dp[i] = 0
然後，檢查其反數的所有子序列
則 ans = dp[i] * dp[j], i, j disjiont.
例如:
10001
01110 => 找其子序列
https://cp-algorithms.com/algebra/all-submasks.html
心得
一開始有想到bitmask, 也想到用暴力法把所有可能記錄下來, 但找反數的所有子序列不知道為啥就卡死了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public:
int pali_length(string &s, int mask) {
int l = 0;
int r = s.size();
int res = 0;
while(l <= r) {
if((mask & (1 << l)) == 0) {
l++;
}
else if((mask & (1 << r)) == 0) {
r--;
}
else if(s[l] != s[r]) {
return 0;
}
else{
res = (res + 1 + (l == r? 0:1));
l++;
r--;
}
}
return res;
}
int maxProduct(string s) {
int res = 0, n = s.size(), mask = (1 << n) - 1;
int dp[4096] = {};
for(int i = 1; i <= mask; i++) {
dp[i] = pali_length(s, i);
// if(dp[i] == 3)cout << dp[i] << endl;
}
for(int i = mask; i; i--) {
if(dp[i] * (n - dp[i]) > res) {
for(int j = mask ^ i; j; j = (j - 1) & (mask ^ i) ) {
res = max(res, dp[j] * dp[i]);
}
}
}
return res;
}
};
|
