C++에서 0과 1의 최대 세그먼트 길이

문제 설명

1과 0으로 구성된 문자열이 주어집니다. 작업은 각 세그먼트의 1이 0보다 크도록 문자열 세그먼트의 최대 길이를 찾는 것입니다.

예시

입력 문자열이 "10111000001011"이면 다음과 같이 12가 됩니다. -

• 첫 번째 세그먼트의 길이는 7 10111000001011입니다.
• 두 번째 세그먼트의 길이는 5 10111000001011입니다.
• 총 길이는 (세그먼트 1 + 세그먼트 2) =(7 + 5) =12의 길이입니다.

알고리즘

• 시작 ==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