美团 2021 届秋季校园招聘—偏爱字母（转化+动态规划）

题目链接：偏爱字母
\qquad 小美喜欢字母 E ，讨厌字母 F 。在小美生日时，小团送了小美一个仅包含字母 E 和 F 的字符串，小美想从中选出一个包含字母 E 数量与字母 F 数量之差最大的子串。
\qquad 子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如 abcab 是 fabcab 的子串，而不是 abcad 的子串。我们将空串看作所有字符串的子串。

思路：

\qquad 根据题意可以推出字母 E 对答案的贡献是正向的，多一个答案就加1；字母 F 对答案的贡献是负向的，多一个答案就减1。那么将字符串中所有的 E 替换为1，所有的 F 替换为-1，问题就转化为给定一个只包含1和-1的数组，求一个和最大的子串。用最大子段和的思路求解即可。

代码：

# include
# include
using namespace std;const int maxn =  300000 + 5;
int a[maxn];
int dp[maxn];
int n;
int main()
{cin >> n;string tp;cin >> tp;for(int i = 0;i < n; ++i){if(tp[i] == 'E') a[i] = 1;else if(tp[i] == 'F') a[i] = -1;}dp[0] = max(a[0], 0);int ans = 0;for(int i = 1;i < n; ++i){dp[i] = max(a[i], dp[i - 1] + a[i]);if(dp[i] > ans) ans = dp[i];}cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！