minimiser le sous-tableau continious maximale dans le tableau de 0/1

Question

Algo question

tableau binaire de 0/1 donné
Dans une opération je peux retourner tout tableau [index] de la matrice-à-dire 0-> 1 ou 1-> 0 si le but est de réduire au minimum le lenth maximum de continious 1 de ou des 0 en utilisant atmost k flips

par exemple si 11111 si le tableau et k = 1, le mieux est de faire ensemble comme 11011
et valeur minimale de 1 ou 0 maximum continu est 2

pour 111.110.111.111 et k = 3 ans est 2

J'ai essayé Brute Force (en essayant différentes positions flips), mais ce ne est pas efficace

Je pense Greedy, mais ne peut pas comprendre exactement
peut vous me aider pour s'il vous plaît algo, O (n) ou similaire

Answer 1

une solution pourrait être conçue en lisant chaque bit dans l'ordre et l'enregistrement de la taille de chaque groupe continu de 1 dans une liste A.

Une fois terminé le remplissage A, on peut suivre l'algorithme rapporté par le pseudo-code ci-dessous:

result = N 
for i = 1 to N 
    flips_needed = 0 
    for a in A: 
     flips_needed += <number of flips needed to make sure largest group remaining in a is of size i> 
    if k >= flips_needed: 
     result = flips_needed 
     break 
return result 

N est le nombre de bits dans la totalité de la séquence initiale.

L'algorithme ci-dessus fonctionne en divisant les groupes de 1 en tailles d'au plus i. Chaque fois que cela nécessite < = k, nous avons le résultat que nous recherchons, car je commence à partir de 1 et monte. (c'est-à-dire lorsque nous avons trouvé flips_needed < = k, nous savons que les groupes de 1 sont aussi minimes que possible)