# 找到要翻轉的零，以使連續的 1 的數目最大化 > 原文： [https://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/](https://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized/) 給定一個二進制數組和一個整數`m`，找到零翻轉的位置，這將創建數組中連續的 1 的最大數量。 **示例**： ``` Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1} m = 2 Output: 5 7 We are allowed to flip maximum 2 zeroes. If we flip arr[5] and arr[7], we get 8 consecutive 1's which is maximum possible under given constraints Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1} m = 1 Output: 7 We are allowed to flip maximum 1 zero. If we flip arr[7], we get 5 consecutive 1's which is maximum possible under given constraints. Input: arr[] = {0, 0, 0, 1} m = 4 Output: 0 1 2 Since m is more than number of zeroes, we can flip all zeroes. ``` 來源： [http://www.careercup.com/question?id=5106425965576192](http://www.careercup.com/question?id=5106425965576192) **簡單解決方案**是通過運行兩個循環來考慮每個子數組。 對于每個子數組，計數其中的零個數。 返回具有`m`個或更少零個的最大大小子數組。 該解決方案的時間復雜度為 `O(n^2)`。 **更好的解決方案**是使用輔助空間解決`O(n)`時間的問題。 對于 0 的所有位置，分別計算`left[]`和`right[]`，它們分別定義`i`的左側和`i`的右側連續 1 的數量。 例如，對于`arr[] = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1}`和`m = 1`，`left[2] = 2`和`right[2] = 2`，`left[5] = 2`，`right[5] = 0`，`left[6] = 0`，`right[6] = 3`。 可以通過遍歷一次數組并跟蹤最后一次看到的 1 和最后一次看到的 0 來填充`left[]`和`right[]`的時間為`O(n)`。在填充`left[]`和`right[]`的同時，我們還將全零的索引存儲在第三個數組，`zeroes[]`。 對于上面的示例，此第三個數組存儲`{2, 5, 6}` 現在遍歷`zeros[]`，對于該數組中的所有連續`m`個條目，計算可產生的 1s 之和。 可以使用`left[]`和`right[]`在`O(n)`中完成此步驟。 有效的**解決方案**可以解決`O(n)`時間和`O(1)`空間中的問題。 這個想法是對給定的數組使用滑動窗口。 解決方案取自[此處](http://www.careercup.com/question?id=5106425965576192)。 讓我們使用一個覆蓋從索引`wL`到索引`wR`的窗口。 設窗口內的零數為`zeroCount`。 我們維護的窗口中最多包含`m`個零。 主要步驟是： + 當`zeroCount`不超過`m`時：向右擴展窗口（`wR++`）并更新`count zeroCount`。 + 當`zeroCount`超過` m `時，從左側縮小窗口（`wL++`），更新`zeroCount`； + 一路更新最寬的窗口。 輸出零的位置在最佳窗口內。 以下是該想法的實現。 ## C++ ```cpp // C++ program to find positions of zeroes flipping which // produces maximum number of xonsecutive 1's #include<bits/stdc++.h> using namespace std; // m is maximum of number zeroes allowed to flip // n is size of array void findZeroes(int arr[], int n, int m) { ????// Left and right indexes of current window ????int wL = 0, wR = 0;? ????// Left index and size of the widest window? ????int bestL = 0, bestWindow = 0;? ????// Count of zeroes in current window ????int zeroCount = 0;? ????// While right boundary of current window doesn't cross? ????// right end ????while (wR < n) ????{ ????????// If zero count of current window is less than m, ????????// widen the window toward right ????????if (zeroCount <= m) ????????{ ????????????if (arr[wR] == 0) ??????????????zeroCount++; ????????????wR++; ????????} ????????// If zero count of current window is more than m, ????????// reduce the window from left ????????if (zeroCount > m) ????????{ ????????????if (arr[wL] == 0) ??????????????zeroCount--; ????????????wL++; ????????} ????????// Updqate widest window if this window size is more ????????if ((wR-wL > bestWindow) && (zeroCount<=m)) ????????{ ????????????bestWindow = wR-wL; ????????????bestL = wL; ????????} ????} ????// Print positions of zeroes in the widest window ????for (int i=0; i<bestWindow; i++) ????{ ????????if (arr[bestL+i] == 0) ???????????cout << bestL+i << " "; ????} } // Driver program int main() { ???int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1}; ???int m = 2; ???int n =? sizeof(arr)/sizeof(arr[0]); ???cout << "Indexes of zeroes to be flipped are "; ???findZeroes(arr, n, m); ???return 0; } ```