Độ dài đoạn lớn nhất của 0 và 1 trong C++

Đề bài

Cho chuỗi chỉ chứa 0 và 1. Nhiệm vụ: tìm độ dài lớn nhất của các đoạn của chuỗi sao cho số lượng 1 trong mỗi đoạn lớn hơn 0.

Ví dụ

Nếu chuỗi đầu vào là "10111000001011" thì kết quả là 12:

• Đoạn 1: độ dài 7 → 1011100
• Đoạn 2: độ dài 5 → 0001011
• Tổng độ dài = 7 + 5 = 12

Thuật toán (Đệ quy có nhớ - DP)

1. Nếu start == n trả về 0
2. Duyệt từ start đến n, tính cho từng mảng con
3. Đếm số 1 và số 0
4. Nếu số 1 > số 0: gọi đệ quy cho chỉ số (k+1) và cộng thêm độ dài còn lại (k-start+1)
5. Ngược lại: chỉ gọi đệ quy cho chỉ số tiếp theo (k+1)
6. Trả về dp[start]

Chương trình C++

#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, 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;
}

Kết quả

Maximum length of segment = 12

Giải thích

Đây là bài toán quy hoạch động tìm tổng độ dài lớn nhất của các đoạn không chồng chéo, mỗi đoạn có số 1 nhiều hơn số 0.