Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

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

Nhiệm vụ: tìm xâu con của xâu nhị phân cho trước sao cho hiệu giữa số 0 và số 1 lớn nhất, độ phức tạp O(n).

Ví dụ 1

Đầu vào** –

str = "10010110"

Đầu ra** – 2

Giải thích** – Xâu con vị trí 1-4 ("0010"): 3 số 0, 1 số 1, hiệu = 2.

Ví dụ 2

Đầu vào** –

str = "00000"

Đầu ra** – 5

Phương pháp O(n) - Kadane biến thể

  • Tạo mảng arr kích thước n+1, khởi tạo 0.
  • Duyệt j=1..n: nếu str[j-1]=='1' thì arr[j] = max(arr[j-1]-1, -1); ngược lại arr[j] = max(arr[j-1]+1, 1).
  • Kết quả = max của mảng arr.

Ý tưởng: arr[j] lưu hiệu lớn nhất kết thúc tại vị trí j. Nếu gặp '1' (giá trị -1), hoặc mở rộng dãy cũ, hoặc bắt đầu mới tại -1. Tương tự cho '0' (+1).

Ví dụ

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

Đầu ra

2