C ++中0和1的最大段长度
问题陈述
给定一个由一和零组成的字符串。任务是找到字符串段的最大长度，以使每个段中的数字1大于0
示例
如果输入字符串为“10111000001011”，则答案将为12，如下所示：
第一段的长度为710111000001011
第二段的长度为510111000001011
总长度是（段1+段2）的长度=（7+5）=12
算法
如果start==n，则返回0。
从开始到n运行一个循环，计算每个子数组直到n。
如果character为1，则增加计数1，否则增加计数0。
如果计数1大于0，则递归调用索引（k+1）（即下一个索引）的函数，并添加剩余长度（即k-start+1）。
否则，仅递归调用下一个索引k+1的函数。
返回dp[start]。
示例
#include <bits/stdc++.h>
using namespace std;
int getSegmentWithMaxLength(int start, string str, int n, int dp[]) {
if (start == n) {
return 0;
}
if (dp[start] != -1) {
return dp[start];
}
dp[start] = 0;
int one = 0;
int zero = 0;
int k;
for (k = start; k < n; ++k) {
if (str[k] == '1') {
++one;
} else {
++zero;
} if (one > zero) {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1);
} else {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp));
}
}
return dp[start];
}
int main() {
string str = "10111000001011";
int n = str.size();
int dp[n + 1];
memset(dp, -1, sizeof(dp));
cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Maximum length of segment = 12