## Max Consecutive Ones III

Given an array A of `0's` and `1's`, and a value K which indicates that you may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1’s.

Example:

``````Input: A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
Output: 6

To obtain the longest contiguous subarray of 1s, you can flip the 0s at index 5 and 10 to 1s:
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
``````

## Max Consecutive Ones III solution in Java

This problem can be solved using the two pointer sliding window technique.

• Initialize two pointers (indexes): `left = 0` and `right = 0`.
• Initialize a variable `numConversions` to keep track of the number of conversions done from `0` to `1`.
• Iterate over the array until the `right` index reaches the end of the array.
• If `a[right] == 0`, then we need to flip this element to `1` to obtain a contiguous subarray of 1s. Therefore, we increment the `numConversions` value.
• If `numConversions` is greater than the number of allowed conversions, then we can’t proceed, and we must shift our window by incrementing `left` index until `numConversions` becomes equal to the number of allowed conversions.
• In every iteration, we check if the current length of longest contiguous subarray of 1s is greater than the previous value, and we set the longest length accordingly.
``````class MaxConsecutiveOnesIII {
private static int findMaxConsecutiveOnes(int[] a, int k) {
int maxOnes = Integer.MIN_VALUE;
int numConversions = 0;
int left = 0, right = 0;

for(right = 0; right < a.length; right++) {
if(a[right] == 0) {
numConversions++;
}

while(numConversions > k) {
if(a[left] == 0) {
numConversions--;
}
left++;
}

maxOnes = Math.max(maxOnes, right-left+1);
}

return maxOnes;
}

public static void main(String[] args) {
int[] a = new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
int k = 2;
int result = findMaxConsecutiveOnes(a, k);
System.out.printf("Length of longest contiguous subarray containing only 1s = %d", result);
}
}
``````
``````# Output
Length of longest contiguous subarray containing only 1s = 6
``````