ความต่างสูงสุดของศูนย์และหนึ่งในสตริงไบนารีใน C++

ภารกิจคือการหา sub-string จากสตริงไบนารีที่กำหนด และหาความต่างสูงสุดระหว่างจำนวนศูนย์และหนึ่ง

ตัวอย่าง

อินพุต

str = "100100110"

เอาต์พุต

2

คำอธิบาย

ใน sub-array ตำแหน่ง 1 ถึง 5 ("00100") ความต่างระหว่างศูนย์และหนึ่ง = 4 - 1 = 3 ซึ่งเป็นค่าสูงสุดที่หาได้

อินพุต

str = "00000"

เอาต์พุต

5

แนวทางที่ใช้ในโปรแกรมด้านล่าง

• ใน main() สร้าง string str เก็บสตริงไบนารี และตัวแปร int size เก็บขนาด ส่งทั้งคู่เข้า Max()
• ใน Max() ตรวจสอบก่อนว่าทุกตัวเป็น 1 หรือไม่ เรียก One()
• สร้าง One() แบบ bool ตัวแปร int O = 0 ลูป i = 0 ถึง str.size() ถ้า str[i] == '1' เพิ่ม O
• นอกลูป ถ้า O == size คืน true
• กลับ Max() ถ้า One() true คืน -1
• มิฉะนั้น หาความยาว เริ่มต้น int a[100] = {0}
• ลูป i = 0 ถึง size ใส่ a[i] = (str[i] == '0' ? 1 : -1)
• เริ่มต้น int arr[100][3] ใส่ -1 ด้วย memset เรียก Length(a, str, size, 0, 0, arr)
• ใน Length() ถ้า i >= size คืน 0 (จบสตริง)
• ถ้า arr[i][s] != -1 คืนค่าที่คำนวณไว้ (Memoization)
• ถ้า s == 0 คืน max(a[i] + Length(..., i+1, 1), Length(..., i+1, 0))
• มิฉะนั้น คืน max(a[i] + Length(..., i+1, 1), 0)

ตัวอย่างโปรแกรม

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

เอาต์พุต

3