สมมติว่ามีอาร์เรย์ไบนารี เราต้องหาจำนวน 1 ที่ติดกันมากที่สุดในอาร์เรย์นี้ หากเราสามารถพลิก 0 ได้สูงสุด 1 ตัว
เช่น ถ้าอินพุทเป็น [1,0,1,1,0] ผลลัพธ์จะเป็น 4 เพราะถ้าพลิก 0 ตัวแรก จะได้ 1 ติดกันมากที่สุด 4 ตัว หลังจากพลิกแล้ว จำนวน 1 ติดกันสูงสุดคือ 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
ret := 1, n := ขนาดของ nums
ถ้า n เป็นศูนย์ แล้ว −
คืนค่า 0
j := 0, zero := 0
ลูป i := 0 ถึง n-1 ทำ −
ถ้า nums[i] เป็น 0 แล้ว −
เพิ่ม zero ขึ้น 1
ลูป while (j <= i และ zero > 1) ทำ −
ถ้า nums[j] เป็น 0 แล้ว −
ลด zero ลง 1
เพิ่ม j ขึ้น 1
ret := ค่าสูงสุดของ ret และ (i - j + 1)
คืนค่า ret
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int ret = 1; int n = nums.size(); if (!n) return 0; int j = 0; int zero = 0; for (int i = 0; i < n; i++) { if (nums[i] == 0) { zero++; } while (j <= i && zero > 1) { if (nums[j] == 0) { zero--; } j++; } ret = max(ret, i - j + 1); } return ret; } }; main(){ Solution ob; vector<int> v = {1,0,1,1,1,0,1,1}; cout << (ob.findMaxConsecutiveOnes(v)); } อินพุท
{1,0,1,1,1,0,1,1} เอาต์พุท
6
