Нахождение самой длинной последовательности «1» в двоичном массиве путем замены любого «0» на «1»

Question

У меня есть массив, который состоит только из 0 и 1.Задача состоит в том, чтобы найти индекс 0 , замена которого на 1 приводит к максимально длинной последовательности единиц для данного массива.Решение должно работать в течение O (n) времени и O (1) пробела.

Например:

Array - 011101101001
Ответ - 4 (при этом получается 0111 1 1101001)

Мой подход дает мне результат лучше, чем O (n2), но время ожидания увеличиваетсястроковые входы.

int findIndex(int[] a){

    int maxlength = 0; int maxIndex= -1;
    int n=a.length;
    int i=0; 
    while(true){

        if( a[i] == 0 ){
            int leftLenght=0;
            int j=i-1;
            //finding count of 1s to left of this zero
            while(j>=0){
                if(a[j]!=1){
                    break;
                }
                leftLenght++;
                j--;
            }

            int rightLenght=0;
            j=i+1;
            // finding count of 1s to right of this zero
            while(j<n){
                if(a[j]!=1){
                    break;
                }
                rightLenght++;
                j++;
            }

            if(maxlength < leftLenght+rightLenght + 1){
                maxlength = leftLenght+rightLenght + 1;
                maxIndex = i;
            }
        }
        if(i == n-1){
            break;
        }
        i++;
    }
    return maxIndex;
}

Answer 1

Я считаю, что проблему можно решить, просто поддерживая переменную, в которой хранятся последние следы 1, которые мы видели до достижения значения «0».

int last_trail = 0;
int cur_trail = 0;
int last_seen = -1;
int ans = 0, maxVal = 0;
for(int i = 0; i < a.size(); i++) {
    if(a[i] == '0') {
        if(cur_trail + last_trail + 1 >  maxVal) {
            maxVal = cur_trail + last_trail + 1;
            ans = last_seen;
        }
        last_trail = cur_trail;
        cur_trail = 0;
        last_seen = i; 
    } else {
        cur_trail++;
    }
}
if(cur_trail + last_trail + 1 >  maxVal && last_seen > -1) {
    maxVal = cur_trail + last_trail + 1;
    ans = last_seen;
}

Answer 2

Это можно решить с помощью техники, известной как два указателя .Большинство двухочковых указателей используют O (1) пробел и O (n) время.

Код: https://www.ideone.com/N8bznU

#include <iostream>
#include <string>
using namespace std;


int findOptimal(string &s) {
    s += '0'; // add a sentinel 0
    int best_zero = -1;
    int prev_zero = -1;
    int zeros_in_interval = 0;
    int start = 0;
    int best_answer = -1;
    for(int i = 0; i < (int)s.length(); ++i) {
        if(s[i] == '1') continue;
        else if(s[i] == '0' and  zeros_in_interval == 0) {
            zeros_in_interval++;
            prev_zero = i;
        }
        else if(s[i] == '0' and zeros_in_interval == 1) {
            int curr_answer =  i - start; // [start, i) only contains one 0
            cout << "tried this : [" << s.substr(start, i - start) << "]\n";
            if(curr_answer > best_answer) {
                best_answer = curr_answer;
                best_zero = prev_zero;
            }
            start = prev_zero + 1;
            prev_zero = i;
        }
    }
    cout << "Answer = " << best_zero << endl;
    return best_zero;
}
int main() {
    string input = "011101101001";
    findOptimal(input);
    return 0;
}

Это реализация в C ++.Вывод выглядит так:

tried this : [0111]
tried this : [111011]
tried this : [1101]
tried this : [10]
tried this : [01]
Answer = 4

Answer 3

Подход прост, вам просто нужно поддерживать два числа во время итерации по массиву, текущий счетчик непрерывного блока, равного единице, и последний непрерывный блок, равный нулю.

Примечание: это решение предполагает, что в массиве будет хотя бы один ноль, в противном случае он вернет -1

int cal(int[]data){
    int last = 0;
    int cur = 0;
    int max = 0; 
    int start = -1; 
    int index = -1;
    for(int i = 0; i < data.length; i++){
        if(data[i] == 0){
           if(max < 1 + last + cur){
              max = 1 + last + cur;
              if(start != -1){
                index = start;
              }else{
                index = i;
              }
           }
           last = cur;
           start = i;
           cur = 0;  
        }else{
            cur++;
        }
    }
    if(cur != 0 && start != -1){
       if(max < 1 + last + cur){
          return start;
       }
    }     
    return index;
}

O (n) время, O (1) пробел

Живая демоверсия: https://ideone.com/1hjS25