สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ N องค์ประกอบเหล่านี้เป็น 0 หรือ 1 ค้นหาตำแหน่งของ 0 ที่จะแทนที่ด้วย 1 เพื่อให้ได้ลำดับที่ต่อเนื่องกันที่ยาวที่สุดของ 1 วินาที สมมติว่าอาร์เรย์เป็นเหมือน arr =[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] ดัชนีเอาต์พุตคือ 9 การแทนที่ 0 ด้วย 1 ที่ดัชนี 9 ทำให้ ลำดับต่อเนื่องกันสูงสุดของ 1s
เราต้องติดตามสามดัชนี ดัชนีปัจจุบัน (สกุลเงิน) ดัชนีศูนย์ก่อนหน้า (pz) และดัชนีศูนย์ก่อนหน้า (ppz) ตอนนี้ให้สำรวจอาร์เรย์เมื่อองค์ประกอบอาร์เรย์เป็น 0 จากนั้นคำนวณความแตกต่างระหว่าง curr และ ppz หากความแตกต่างมากกว่าค่าสูงสุด ให้อัปเดตค่าสูงสุด ในที่สุดก็ส่งคืนดัชนีของ prev_zero โดยมีค่าความแตกต่างสูงสุด
ตัวอย่าง
#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
int count_max = 0;
int index;
int pz = -1;
int ppz = -1;
for (int curr=0; curr<n; curr++) {
if (arr[curr] == 0) {
if (curr - ppz > count_max){
count_max = curr - ppz;
index = pz;
}
ppz = pz;
pz = curr;
}
}
if (n-ppz > count_max)
index = pz;
return index;
}
int main() {
bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Index of 0 to be replaced is "<< findIndex(arr, n);
} ผลลัพธ์
Index of 0 to be replaced is 9
