Dada una array binaria, encuentre el número máximo de ceros en una array con un giro de un subarreglo permitido. Una operación de volteo cambia todos los 0 a 1 y los 1 a 0.
Ejemplos:
Input : arr[] = {0, 1, 0, 0, 1, 1, 0}
Output : 6
We can get 6 zeros by flipping the subarray {4, 5}
Input : arr[] = {0, 0, 0, 1, 0, 1}
Output : 5
Método 1 (Simple: O(n 2 )): Una solución simple es considerar todos los subarreglos y encontrar un subarreglo con un valor máximo de (recuento de 1s) – (recuento de 0s) . Sea este valor max_diff. Finalmente, devuelva el recuento de ceros en la array original más max_diff.
C++
// C++ program to maximize number of zeroes in a
// binary array by at most one flip operation
#include<bits/stdc++.h>
using namespace std;
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
int findMaxZeroCount(bool arr[], int n)
{
// Initialize max_diff = maximum of (Count of 0s -
// count of 1s) for all subarrays.
int max_diff = 0;
// Initialize count of 0s in original array
int orig_zero_count = 0;
// Consider all Subarrays by using two nested two
// loops
for (int i=0; i<n; i++)
{
// Increment count of zeros
if (arr[i] == 0)
orig_zero_count++;
// Initialize counts of 0s and 1s
int count1 = 0, count0 = 0;
// Consider all subarrays starting from arr[i]
// and find the difference between 1s and 0s.
// Update max_diff if required
for (int j=i; j<n; j++)
{
(arr[j] == 1)? count1++ : count0++;
max_diff = max(max_diff, count1 - count0);
}
}
// Final result would be count of 0s in original
// array plus max_diff.
return orig_zero_count + max_diff;
}
// Driver program
int main()
{
bool arr[] = {0, 1, 0, 0, 1, 1, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << findMaxZeroCount(arr, n);
return 0;
}
Java
// Java code for Maximize number of 0s by flipping
// a subarray
class GFG {
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
public static int findMaxZeroCount(int arr[], int n)
{
// Initialize max_diff = maximum of (Count of 0s -
// count of 1s) for all subarrays.
int max_diff = 0;
// Initialize count of 0s in original array
int orig_zero_count = 0;
// Consider all Subarrays by using two nested two
// loops
for (int i=0; i<n; i++)
{
// Increment count of zeros
if (arr[i] == 0)
orig_zero_count++;
// Initialize counts of 0s and 1s
int count1 = 0, count0 = 0;
// Consider all subarrays starting from arr[i]
// and find the difference between 1s and 0s.
// Update max_diff if required
for (int j = i; j < n; j ++)
{
if(arr[j] == 1)
count1++;
else count0++;
max_diff = Math.max(max_diff, count1 - count0);
}
}
// Final result would be count of 0s in original
// array plus max_diff.
return orig_zero_count + max_diff;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {0, 1, 0, 0, 1, 1, 0};
System.out.println(findMaxZeroCount(arr, arr.length));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to maximize number of # zeroes in a binary array by at most # one flip operation # A Kadane's algorithm based solution # to find maximum number of 0s by # flipping a subarray. def findMaxZeroCount(arr, n): # Initialize max_diff = maximum # of (Count of 0s - count of 1s) # for all subarrays. max_diff = 0 # Initialize count of 0s in # original array orig_zero_count = 0 # Consider all Subarrays by using # two nested two loops for i in range(n): # Increment count of zeros if arr[i] == 0: orig_zero_count += 1 # Initialize counts of 0s and 1s count1, count0 = 0, 0 # Consider all subarrays starting # from arr[i] and find the # difference between 1s and 0s. # Update max_diff if required for j in range(i, n): if arr[j] == 1: count1 += 1 else: count0 += 1 max_diff = max(max_diff, count1 - count0) # Final result would be count of 0s # in original array plus max_diff. return orig_zero_count + max_diff # Driver code arr = [ 0, 1, 0, 0, 1, 1, 0 ] n = len(arr) print(findMaxZeroCount(arr, n)) # This code is contributed by stutipathak31jan
C#
// C# code for Maximize number of 0s by
// flipping a subarray
using System;
class GFG{
// A Kadane's algorithm based solution
// to find maximum number of 0s by
// flipping a subarray.
public static int findMaxZeroCount(int []arr,
int n)
{
// Initialize max_diff = maximum of
// (Count of 0s - count of 1s) for
// all subarrays.
int max_diff = 0;
// Initialize count of 0s in
// original array
int orig_zero_count = 0;
// Consider all Subarrays by
// using two nested two loops
for(int i = 0; i < n; i++)
{
// Increment count of zeros
if (arr[i] == 0)
orig_zero_count++;
// Initialize counts of 0s and 1s
int count1 = 0, count0 = 0;
// Consider all subarrays starting
// from arr[i] and find the difference
// between 1s and 0s.
// Update max_diff if required
for(int j = i; j < n; j ++)
{
if(arr[j] == 1)
count1++;
else count0++;
max_diff = Math.Max(max_diff,
count1 - count0);
}
}
// Final result would be count of 0s in original
// array plus max_diff.
return orig_zero_count + max_diff;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 0, 1, 0, 0, 1, 1, 0 };
Console.WriteLine(
findMaxZeroCount(arr, arr.Length));
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program to maximize number of zeroes in a
// binary array by at most one flip operation
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
function findMaxZeroCount(arr, n)
{
// Initialize max_diff = maximum of (Count of 0s -
// count of 1s) for all subarrays.
let max_diff = 0;
// Initialize count of 0s in original array
let orig_zero_count = 0;
// Consider all Subarrays by using two nested two
// loops
for (let i=0; i<n; i++)
{
// Increment count of zeros
if (arr[i] == 0)
orig_zero_count++;
// Initialize counts of 0s and 1s
let count1 = 0, count0 = 0;
// Consider all subarrays starting from arr[i]
// and find the difference between 1s and 0s.
// Update max_diff if required
for (let j=i; j<n; j++)
{
(arr[j] == 1)? count1++ : count0++;
max_diff = Math.max(max_diff, count1 - count0);
}
}
// Final result would be count of 0s in original
// array plus max_diff.
return orig_zero_count + max_diff;
}
// Driver program
let arr = [0, 1, 0, 0, 1, 1, 0];
let n = arr.length;
document.write(findMaxZeroCount(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
6
Método 2 (Eficiente: O(n)): Este problema se puede reducir al problema de suma de subarreglo más grande . La idea es considerar cada 0 como -1 y cada 1 como 1, encontrar la suma de la suma de subarreglo más grande en este arreglo modificado. Esta suma es nuestro max_diff requerido (conteo de 0s – conteo de 1s en cualquier subarreglo). Finalmente, devolvemos el max_diff más el conteo de ceros en la array original.
C++
// C++ program to maximize number of zeroes in a
// binary array by at most one flip operation
#include<bits/stdc++.h>
using namespace std;
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
int findMaxZeroCount(bool arr[], int n)
{
// Initialize count of zeros and maximum difference
// between count of 1s and 0s in a subarray
int orig_zero_count = 0;
// Initiale overall max diff for any subarray
int max_diff = 0;
// Initialize current diff
int curr_max = 0;
for (int i=0; i<n; i++)
{
// Count of zeros in original array (Not related
// to Kadane's algorithm)
if (arr[i] == 0)
orig_zero_count++;
// Value to be considered for finding maximum sum
int val = (arr[i] == 1)? 1 : -1;
// Update current max and max_diff
curr_max = max(val, curr_max + val);
max_diff = max(max_diff, curr_max);
}
max_diff = max(0, max_diff);
return orig_zero_count + max_diff;
}
// Driver program
int main()
{
bool arr[] = {0, 1, 0, 0, 1, 1, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << findMaxZeroCount(arr, n);
return 0;
}
Java
// Java code for Maximize number of 0s by
// flipping a subarray
class GFG {
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
public static int findMaxZeroCount(int arr[], int n)
{
// Initialize count of zeros and maximum difference
// between count of 1s and 0s in a subarray
int orig_zero_count = 0;
// Initiale overall max diff for any subarray
int max_diff = 0;
// Initialize current diff
int curr_max = 0;
for (int i = 0; i < n; i ++)
{
// Count of zeros in original array (Not related
// to Kadane's algorithm)
if (arr[i] == 0)
orig_zero_count ++;
// Value to be considered for finding maximum sum
int val = (arr[i] == 1)? 1 : -1;
// Update current max and max_diff
curr_max = Math.max(val, curr_max + val);
max_diff = Math.max(max_diff, curr_max);
}
max_diff = Math.max(0, max_diff);
return orig_zero_count + max_diff;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {0, 1, 0, 0, 1, 1, 0};
System.out.println(findMaxZeroCount(arr, arr.length));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to maximize number # of zeroes in a binary array by at # most one flip operation # A Kadane's algorithm based solution # to find maximum number of 0s by # flipping a subarray. def findMaxZeroCount(arr, n): # Initialize count of zeros and # maximum difference between count # of 1s and 0s in a subarray orig_zero_count = 0 # Initialize overall max diff # for any subarray max_diff = 0 # Initialize current diff curr_max = 0 for i in range(n): # Count of zeros in original # array (Not related to # Kadane's algorithm) if arr[i] == 0: orig_zero_count += 1 # Value to be considered for # finding maximum sum val = 1 if arr[i] == 1 else -1 # Update current max and max_diff curr_max = max(val, curr_max + val) max_diff = max(max_diff, curr_max) max_diff = max(0, max_diff) return orig_zero_count + max_diff # Driver code arr = [ 0, 1, 0, 0, 1, 1, 0 ] n = len(arr) print(findMaxZeroCount(arr, n)) # This code is contributed by stutipathak31jan
C#
// C# code for Maximize number of 0s by
// flipping a subarray
using System;
class GFG{
// A Kadane's algorithm based solution to find maximum
// number of 0s by flipping a subarray.
public static int findMaxZeroCount(int []arr, int n)
{
// Initialize count of zeros and maximum difference
// between count of 1s and 0s in a subarray
int orig_zero_count = 0;
// Initiale overall max diff for any subarray
int max_diff = 0;
// Initialize current diff
int curr_max = 0;
for (int i = 0; i < n; i ++)
{
// Count of zeros in original array (Not related
// to Kadane's algorithm)
if (arr[i] == 0)
orig_zero_count ++;
// Value to be considered for finding maximum sum
int val = (arr[i] == 1)? 1 : -1;
// Update current max and max_diff
curr_max = Math.Max(val, curr_max + val);
max_diff = Math.Max(max_diff, curr_max);
}
max_diff = Math.Max(0, max_diff);
return orig_zero_count + max_diff;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {0, 1, 0, 0, 1, 1, 0};
Console.WriteLine(findMaxZeroCount(arr, arr.Length));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program to
// maximize number of zeroes in a
// binary array by at most one flip operation
// A Kadane's algorithm
// based solution to find maximum
// number of 0s by flipping a subarray.
function findMaxZeroCount(arr, n)
{
// Initialize count of
// zeros and maximum difference
// between count of 1s and 0s in
// a subarray
var orig_zero_count = 0;
// Initiale overall max diff for any subarray
var max_diff = 0;
// Initialize current diff
var curr_max = 0;
for (var i=0; i<n; i++)
{
// Count of zeros in original array
// (Not related to Kadane's algorithm)
if (arr[i] == 0)
orig_zero_count++;
// Value to be considered for
// finding maximum sum
var val;
if (arr[i] == 1)
val=1;
else
val=-1;
// Update current max and max_diff
curr_max = Math.max(val, curr_max + val);
max_diff = Math.max(max_diff, curr_max);
}
max_diff = Math.max(0, max_diff);
return orig_zero_count + max_diff;
}
var arr = [0, 1, 0, 0, 1, 1, 0];
var n=7;
document.write(findMaxZeroCount(arr, n));
// This Code is Contributed by Harshit Srivastava
</script>
Producción
6
Este artículo es una contribución de Shivam Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA