C ++中0和1的最大段长度

问题陈述

给定一个由一和零组成的字符串。任务是找到字符串段的最大长度，以使每个段中的数字1大于0

示例

如果输入字符串为“ 10111000001011”，则答案将为12，如下所示：

• 第一段的长度为7 10111000001011

• 第二段的长度为5 10111000001011

• 总长度是（段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