C++での0と1のセグメントの最大長

問題の説明

1と0で構成される文字列が与えられます。タスクは、各セグメントの1の数が0より大きくなるように文字列のセグメントの最大長を見つけることです

例

入力文字列が「10111000001011」の場合、答えは次のように12になります-

• 最初のセグメントの長さは710111000001011
• 2番目のセグメントの長さは510111000001011
• 全長は（セグメント1 +セグメント2）=（7 + 5）=12の長さです

アルゴリズム

• start ==nの場合、0を返します。
• 開始からnまでループを実行し、サブアレイごとにnまで計算します。
• 文字が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