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