Tuyên bố vấn đề
Cho một chuỗi bao gồm các số một và các số không. Nhiệm vụ là tìm độ dài tối đa của các đoạn của chuỗi sao cho số 1 trong mỗi đoạn lớn hơn 0
Ví dụ
Nếu chuỗi đầu vào là “10111000001011” thì câu trả lời sẽ là 12 như sau -
- Đoạn đầu tiên có độ dài là 7 10111000001011
- Đoạn thứ hai có độ dài 5 10111000001011
- Tổng độ dài là độ dài của (đoạn 1 + đoạn 2) =(7 + 5) =12
Thuật toán
- Nếu start ==n thì trả về 0.
- Chạy một vòng lặp từ đầu đến n, tính toán cho từng mảng con cho đến n.
- Nếu ký tự là 1 thì tăng số lượng của 1 ký tự khác tăng số lượng là 0.
- Nếu số lượng 1 lớn hơn 0, hãy gọi đệ quy hàm cho chỉ mục (k + 1) tức là chỉ mục tiếp theo và thêm độ dài còn lại, tức là k-start + 1.
- Khác chỉ gọi một cách đệ quy hàm cho chỉ mục tiếp theo k + 1.
- Trả về dp [start].
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Maximum length of segment = 12