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

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

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

ตัวอย่าง

อินพุต

str = "10010110"

เอาต์พุต

คำอธิบาย

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

อินพุต

str = "00000"

เอาต์พุต

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

ใน main() สร้าง string str เก็บสตริงไบนารี ประกาศอาร์เรย์ int arr[str.length()+1]
ตั้งค่า arr[] = 0 ด้วย memset(arr,0,sizeof(arr))
ลูป j = 1 ถึง j <= str.length()
ถ้า str[j-1] == '1' ใส่ arr[j] = max(arr[j-1] - 1, -1)
มิฉะนั้น ใส่ arr[j] = max(arr[j-1] + 1, 1)
นอกลูป พิมพ์ค่าสูงสุดด้วย *max_element(arr+1, arr+str.length()+1)

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

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

int main() {
    string str = "10010110";
    int arr[str.length() + 1];
    memset(arr, 0, sizeof(arr));
    for(int j = 1; j <= str.length(); j++) {
        if(str[j-1] == '1')
            arr[j] = max(arr[j-1] - 1, -1);
        else
            arr[j] = max(arr[j-1] + 1, 1);
    }
    cout << *max_element(arr + 1, arr + str.length() + 1);
    return 0;
}