Нужна помощь в понимании алгоритма для самого длинного последовательного элемента в массиве

Question

Мне дан вектор, который содержит двоичное значение. Мне нужно найти самую длинную последовательную серию из 1 во всем векторе. Это тип логики c Я не могу решить. Я могу решить большинство случаев, но не все, что означает, что мой алгоритм неисправен. Мы можем даже изменить порядок вопросов на ЛЮБОЙ тип последовательного значения в любом массиве. Я пробовал подсчитать количество голов и хвостов и до сих пор не могу решить 10/10 случаев.

Я думаю, что алгоритм дает неверный ответ, когда полоса начинается в более поздней части вектора, а не в самой большой streak, начинающийся с первого элемента.

Вот мой алгоритм для задачи запроса полос на основе двоичных значений. Также я понимаю, что значения двух итераторов не самые эффективные, но я хочу упростить мой ответ в моих терминах.

ОБРАЗЕЦ ВХОДА: [1,1,0]

ВЫБОР ВЫБОРА: 2

ОБРАЗЕЦ ВХОДА 2: [1,1,0,0,0,1,1,1]

ВЫБОР ВЫБОРА 2: 3

void getMaxStreaks(vector<int> arr) {
int largest_streak{0};
int streak_counter{0};

for(int i = 0; i <= arr.size() - 1; i++){
if(arr[i] == 1){
    streak_counter = 1;
}
    for(int j = i + 1; j <= arr.size() -1; j++){
        if(arr[i] == 1 && arr[j] == 1){
            streak_counter++;
        }

        else if(arr[i] == 1 && arr[j] == 0){
            if(streak_counter > largest_streak){
            largest_streak = streak_counter;
            streak_counter = 0;
            }
        }

    }
    if(streak_counter > largest_streak){
        largest_streak = streak_counter;
        streak_counter = 0;
    }
}

Answer 1

Вот немного скучный ответ. Я уверен, что вы могли бы упростить это еще больше, но все логи c здесь.

Есть ряд вещей, которые вы делали неправильно:

1. Ваш массив доступ начался с 1, int i = 1, а не 0, поэтому вы пропустили первое значение в массиве.
2. Вы можете просто написать i
3. Вы излишне проверяли, завершен ли массив с помощью i! = Arr.size () - 1, for-l oop предотвратит это.
4. Вы увеличивали streak_counter дважды каждый раз, когда arr [i] == 1, из-за вложенного оператора if.
5. Вы устанавливаете streak_counter в 0 для каждого l oop for-l oop , мешая вам найти полосу более 1.

void streak_checker(vector<int> arr)
{
    int streak_counter{ 0 };
    int largest_streak{ 0 };
    for (int i = 0; i < arr.size(); i++)
    {
        if (arr[i] == 1)
        {
            streak_counter++;
        }
        else
        {
            if (streak_counter > largest_streak)
            {
                largest_streak = streak_counter;
            }
            streak_counter = 0;
        }
    }

    if (streak_counter > largest_streak)
    {
        largest_streak = streak_counter;
    }

    cout << largest_streak;
}

Answer 2

Алгоритм , который вы ищете, в основном:

maxstart = 0, maxsize = 0                 # Initial maximum to date, zero
                                          # size means it'll be replaced by
                                          # any run of ones.
state = 0                                 # Initial state is "processing zeros",
                                          # meaning first one will start a run and
                                          # correctly initialise that run.

curr = 0                                  # For setting start of a run.
for each bit in bit_collection:           # Process every bit.
    if state == 0 and bit == 1:           # Catch transition zero -> one.
        start = curr, size = 1            # Initialise this run of ones.
        state = 1                         # Change state.
    elif state == 1:                      # Processing ones.
        if bit == 0:                      # Catch transition one -> zero.
            if size > maxsize:            # Replace longest if this one was longer.
                maxstart = start
                maxsize = size
        else:                             # Continuing a run of ones, increase size.
            size += 1
    curr += 1                             # Update index for run starts.

if state == 1:                            # Special handling of final run of ones.
    if size > maxsize:                    # Replace longest if this one is longer.
        maxstart = start
        maxsize = size

Это конечный автомат, который игнорирует прогоны 0 и подсчитывает прогоны 1. При любом переходе от 1 к 0 (включая «притворный» в конце коллекции), мы просто проверяем, закончился ли цикл дольше, чем предыдущий, и, если это так, используют этот новый цикл как самое длинное движение вперед.

В конце этого процесса maxstart будет содержать начальный индекс самого большого из них, а maxsize будет содержать счет.