0과 1의 배열 A가 있다고 가정하고 0에서 1까지 K 값까지 업데이트할 수 있습니다. 1만 포함하는 가장 긴(연속) 하위 배열의 길이를 찾아야 합니다. 따라서 A =[1,1,1,0,0,0,1,1,1,1,0]이고 k =2이면 출력은 6이 됩니다. 따라서 2개의 0을 뒤집으면 배열은 다음과 같습니다. [1,1,1,0,0,1,1,1,1,1,1]과 같이 1의 가장 긴 시퀀스의 길이는 6입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=0, j :=0 및 n :=배열 크기 설정
- 0 ~ n – 1 범위의 i에 대해
- 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