查找要翻转的零以便连续1的数目最大化

Question

找到要翻转的零以便连续1的数目最大化。

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

我们被允许翻转最多2个零。如果我们翻转 arr [5]和arr [7]，我们会得到8个连续的1，即在给定约束条件下最大可能值为 。

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

Answer 1

你应该在这里使用滑动窗口的概念 - 使用开始和结束变量来存储范围的索引。每当遇到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; 
    } 

Answer 2

这个问题可以在线性时间为O（N）和线性空间ø来解决（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

这些可以在array.Assuming arr的single traversal计算是原始阵列，下面的伪码做这项工作：

伪代码用于填充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改编之间的[I]应为0，并保持轨道pair的，我们得到以下的最大值：

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

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

left[i]告诉连续的1的数量的i和right[j]位置左告诉连续的1的数目的j位置的右侧和i和j之间连续的1的数目进行计数BE 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; 
     } 
    } 
    } 
    }