找到要翻转的0，使连续1的数量最大化

Question

找到要翻转的0，以使连续1的数量最大化。

Input:   arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
     m = 2
Output:  5 7

允许最多翻转2个0。如果我们翻转Arr[5]和Arr[7]，我们得到8个连续的1在给定约束下的最大可能

现在，如果我们要找到可能的最大1数，是否有可能使用动态规划方法来解决?

Answer 1

这个问题可以在线性时间O(N)和线性空间O(N)中求解。它不是完全成熟的动态规划，但它类似于预计算。

数据结构使用:

1.left :整数数组，长度与给定数组相同。 for every position i :

left[i] = Number of consecutive 1's to the left position i

2.right :整数数组，与给定数组的长度相同。 for every position i :

right[i] = Number of consecutive 1's to the right position i

这些可以在数组的single traversal中计算。假设arr是原始数组，下面的伪代码可以完成这项工作:

填充left array的伪代码

left()
{
        int count = 0;
        for(int i = 0;i < arr length; ++i)
        {
            if(i == 0)
            {
                left[i] = 0;
                if(arr[i] == 1)
                 count++;
                continue;
            }
            else
            {
                left[i] = count;
                if(arr[i] == 1)
                 count++;
                else count = 0;
            }
        }
}

填充right array的伪代码

right()
{
    int count = 0;
    for(int i = arr length - 1;i >= 0; --i)
    {
        if(i == arr length - 1)
        {
            right[i] = 0;
            if(arr[i] == 1)
             count++;
            continue;
        }
        else
        {
            right[i] = count;
            if(arr[i] == 1)
             count++;
            else count = 0;
        }
    }
}

现在我们要做的唯一一件事是:检查(i < j)中所有的位置i和j，使arr[i] = 0和arr[j] = 0，以及在i和j之间没有位置的情况下，arr[i]应该为0，并跟踪我们得到以下最大值的那对:

left[i] + right[j] + right[l]

您也可以使用left[i] + right[j] + left[r]

left[i]表示位置i左边连续1的个数，right[j]表示位置j右边连续1的个数，i和j之间连续1的个数可以被计算为left[r] OR right[l]，因此，我们有两个候选表达式。

这也可以在单遍历中完成，使用以下伪代码:

max_One()
  {
    max = 0;
    l = -1, r = -1;
    for(int i = 0;i < arr length; ++i)
    {
     if(arr[i] == 0)
     { 
        if(l == -1)
         l = i;
        else
        {
            r = i;          
            if(left[l] + right[r] + right[l] > max)
            {
                max = left[l] + right[r] + right[l];                
                left_pos = l;
                right_pos = r;
            }
            l = r;
        }
     }
    }
   }

Answer 2

您应该在这里使用滑动窗口概念-使用开始和结束变量来存储范围的索引。每当遇到0时，增加接收到的0计数器。将其包含在当前长度中…如果0遇到等于m+1，则开始递增直到遇到0。

public static int[] zerosToFlip(int[] input, int m) {
        if (m == 0) return new int[0];
        int[] indices = new int[m];
        int beginIndex = 0;
        int endIndex = 0;
        int maxBeginIndex=0;
        int maxEndIndex=0;
        int zerosIncluded = input[0] == 0 ? 1 : 0;
        for (int i = 1; i < input.length; i++) {
            if (input[i] == 0) {
                if (zerosIncluded == m) {
                    if (endIndex - beginIndex > maxEndIndex - maxBeginIndex){
                        maxBeginIndex = beginIndex;
                        maxEndIndex = endIndex;
                    }
                    while (input[beginIndex] != 0) beginIndex++;
                    beginIndex++;
                } else {
                    zerosIncluded++;
                }
            }
            endIndex++;
        }
        if (endIndex - beginIndex > maxEndIndex - maxBeginIndex){
            maxBeginIndex = beginIndex;
            maxEndIndex = endIndex;
        }
        int j = 0;
        for (int i = maxBeginIndex; i <= maxEndIndex; i++) {
            if (input[i] == 0) {
                indices[j] = i;
                ++j;
            }
        }
        return indices;
    }