Hiệu lớn nhất giữa số 0 và 1 trong xâu nhị phân trong C++

Phương pháp (Đệ quy + Memoization)

• Kiểm tra nếu toàn số 1 → trả về -1.
• Chuyển xâu thành mảng giá trị: '0' → +1, '1' → -1.
• Dùng DP Length(i, state): state=0 (chưa bắt đầu xâu con), state=1 (đang trong xâu con).
• Chuyển trạng thái: lấy phần tử hiện tại + chuyển sang state 1, hoặc bỏ qua (state 0).
• Memoization tránh tính lại.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

bool One(string str, int size) {
    int O = 0;
    for (int i = 0; i < str.size(); i++)
        O += (str[i] == '1');
    return (O == size);
}

int Length(int a[], string str, int size, int i, int s, int arr[][3]) {
    if (i >= size) return 0;
    if (arr[i][s] != -1) return arr[i][s];
    if (s == 0)
        return arr[i][s] = max(a[i] + Length(a, str, size, i+1, 1, arr), Length(a, str, size, i+1, 0, arr));
    else
        return arr[i][s] = max(a[i] + Length(a, str, size, i+1, 1, arr), 0);
}

int Max(string str, int size) {
    if (One(str, size)) return -1;
    int a[100] = { 0 };
    for (int i = 0; i < size; i++)
        a[i] = (str[i] == '0' ? 1 : -1);
    int arr[100][3];
    memset(arr, -1, sizeof arr);
    return Length(a, str, size, 0, 0, arr);
}

int main() {
    string str = "100100110";
    int size = 9;
    cout << Max(str, size);
    return 0;
}

Đầu ra

3