Max Continuous Series of 1s
You are given with an array of 1s
and 0s
. And you are given with an integer M
, which signifies number of flips allowed.
Find the position of zeros
which when flipped will produce maximum continuous series of 1s
.
For this problem, return the indices of maximum continuous series of 1s
in order.
Example:
Input :
Array = {1 1 0 1 1 0 0 1 1 1 }
M = 1
Output :
[0, 1, 2, 3, 4]
If there are multiple possible solutions, return the sequence which has the minimum start index.
public class Solution {
public ArrayList<Integer> maxone(ArrayList<Integer> A, int m) {
int i = 0, j = 0;
int bestLeft = 0;
int bestLen = 0;
int zeroCount = 0;
while (j < A.size()) {
if (zeroCount <= m) {
if (A.get(j).compareTo(0) == 0)
zeroCount++;
j++;
} else if (zeroCount > m) {
if (A.get(i).compareTo(0) == 0)
zeroCount--;
i++;
}
if ((j - i > bestLen) && (zeroCount <= m)) {
bestLen = j - i;
bestLeft = i;
}
}
ArrayList<Integer> ans = new ArrayList<>();
for (i = bestLeft; i < bestLeft + bestLen; i++) {
ans.add(i);
}
return ans;
}
}
Last updated