Самая длинная последовательность из 1 в массиве в C

Question

У меня есть такой массив:

0011011100011111001

Я бы хотел найти самую длинную последовательность единиц в этом массиве, учитывая длину и позицию начальной точки, здесь длина будетбыть 5 и отправной точкой является 12.

Есть идеи, как это сделать?

Answer 1

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

let max_consec = 0
let curr_consec = 0
let i = 0
while i < array.size:
    if array[i] is 1:
        curr_consec++
    else:
        max_consec = Max(max_consec, curr_consec)
        curr_consec = 0
    i++

Немного подумав, выдолжен уметь самостоятельно выяснять, как отслеживать исходную позицию.

Answer 2

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

Answer 3

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

Таблица состояний выглядит следующим образом:

              +----------------------------------------+
              |               lastNum                  |
              +------------------+---------------------+
              |         0        |          1          |
+---------+---+------------------+---------------------+
|         | 0 | Just get next    | Check/update runLen |
|         |   |  character       |  against previous   |
| thisNum +---+------------------+---------------------+
|         | 1 | Store runPos  ,  | Increment runLen    |
|         |   |  set runLen to 0 |                     |
+---------+---+------------------+---------------------+

Так как вас интересуют только 1 последовательностей, начальное состояние имеет lastNum, установленное в ноль, чтобы 1 при запуске правильно начинал цикл. Мы также настроили начальный «самый большой прогон на сегодняшний день», чтобы иметь размер и позицию ноль, чтобы гарантировать, что он будет перезаписан первым реальным прогоном.

В этом методе есть особый крайний случай, потому что мы должны определить, является ли последнее число в списке 1 - если это так, это означает, что в конце списка не было перехода 1 -> 0 для проверки финальный прогон 1 номеров.

Поскольку мы вышли из цикла без проверки этого последнего запуска, мы делаем окончательную проверку , как если бы мы переходили с 1 на 0.

Псевдокод выглядит примерно так. Во-первых, инициализация всех переменных:

# Store the current maximum run of '1' characters (none) and initial state.

var maxLen = 0, maxPos = 0, lastNum = 0

# runLen and runPos will be set in a 0->1 transition before we use them.

var rnLen, runPos

Затем мы можем просто перебрать каждое число в списке и обнаружить переходы, как показано на диаграмме выше:

# Iterate over entire list, one by one.

for curPos = 0 to len(list) - 1:
    # 0 -> 0: do nothing.

    # 0 -> 1: store position, set run length to 1.

    if lastNum == 0 and list[curPos] == 1:
        runPos = curPos
        runLen = 1
    endif

    # 1 -> 1: increment the current run length.

    if lastNum == 1 and list[curPos] == 1:
        runLen = runLen + 1
    endif

    # 1 -> 0: check current run against greatest to date.

    if lastNum == 1 and list[curPos] == 0:
        if runLen > maxLen:
            maxPos = runPos
            maxLen = runLen
        endif
    endif

    # Save current number into lastNum for next iteration.

    lastNum = list[curPos]
endfor

Затем, наконец, обработка вышеупомянутого краевого случая:

# If we finished with a `1`, need to check final run.

if lastNum = 1:
    if runLen > maxLen:
        maxPos = runPos
        maxLen = runLen
    endif
endif