Нахождение максимальных двоичных наборов подпоследовательности, которые имеют равное количество 1 с и 0s

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

Конечно, все игнорируют тот факт, что сохранение целого числа n составляет O (log n) в пространстве, и обрабатывает его как O (1) в космосе. :-) Практически все большие О, включая временные, полны (или, скорее, не содержат) отсутствующих log n факторов, или, что эквивалентно, они предполагают, что n ограничено размер машинного слова, что означает, что вы действительно смотрите на конечную задачу, и все равно O (1) .

брутфорс: начать с максимальной длины массива для подсчета нулей и единиц. если o равно l, все готово. иначе уменьшите длину поиска на 1 и выполните алгоритм для всех подпоследовательностей уменьшенной длины (то есть максимальной длины минус уменьшенной длины) и так далее. остановитесь, когда вычитание равно 0.

Обновление .

Я должен полностью перефразировать свой ответ.(Если вы проголосовали за более раннюю версию, что ж, вас обманули!)

Давайте еще раз резюмируем простой случай, чтобы избавиться от него:

Найдите самый длинный префикс из битовая строка, содержащая равное количество единиц и нулей в множество.

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

Теперь давайте перейдем к более сложной версии проблемы: нам больше не требуется, чтобы подпоследовательности были префиксами - они могут начинаться где угодно.

Поразмыслив, я подумал, что для этого не может быть линейного алгоритма. Например, рассмотрим префикс «111111111111111111 ...». Каждая 1 из них может быть началом самой длинной подпоследовательности, нет кандидата в начальную позицию подпоследовательности, которая доминирует (т.е. всегда дает лучшие решения, чем) любая другая позиция, поэтому мы не можем выбросить ни одну из них (O (N) пробел) и на любом этапе мы должны иметь возможность выбрать лучший старт (который имеет равное количество единиц и нулей относительно текущей позиции) из линейно многих кандидатов за время O (1). Оказывается, это выполнимо , и также легко выполнимо, так как мы можем выбрать кандидата на основе текущей суммы единиц (+1) и нулей (-1), он имеет максимальный размер N, и мы можем сохранить первую позицию, которую мы достигли для каждой суммы, в 2N ячейках - см. ответ pmod ниже (комментарии желтого тумана и геометрическое понимание тоже).

Не сумев обнаружить этот трюк, я заменил быстрый, но ошибочный алгоритм на медленный, но надежный (поскольку правильные алгоритмы предпочтительнее неправильных!):

• Создайте массив A с помощью накопленное количество единиц от начала до этой позиции, например если битовая строка - «001001001», тогда массив будет [0, 0, 1, 1, 1, 2, 2, 2, 3]. Используя это,мы можем проверить в O (1), действительна ли подпоследовательность (i, j) включительно: isValid (i, j) = (j - i + 1 == 2 * (A [j] - A [ i - 1]) , т.е. он действителен, если его длина вдвое превышает количество единиц в нем. Например, подпоследовательность (3,6) действительна, потому что 6 - 3 + 1 == 2 * A [6 ] - A [2] = 4.

• Обычный старый двойной цикл:

  maxSubsLength = 0 для i = от 1 до N - 1 для j = от i + 1 до N if isValid (i, j) ... #maintain maxSubsLength конец end

Это можно немного ускорить, используя ветвление и границу, пропуская последовательности i / j, которые короче текущего maxSubsLength, но асимптотически это все еще O (n ^ 2). Медленно, но с большим плюсом: правильно!

В этой теме ( http://discuss.techinterview.org/default.asp?interview.11.792102.31 ) постер A.F. дал алгоритм, который выполняется за O(n) время и использует O(sqrt(n log n)) битов.

Новое решение: Предположим, что у нас есть для n-битного входного битового массива 2*n-размерный массив для хранения позиции бита. Значит, размер элемента массива должен иметь достаточный размер, чтобы сохранить максимальное число позиций. Для 256-битного входного битового массива необходим массив 256x2 байта (байт достаточен для хранения 255 - максимальной позиции).

Двигаясь от первой позиции битового массива, мы заносим позицию в массив, начиная с середины массива (индекс равен n), используя правило:

1. Увеличиваем позицию, если передан бит "1", и уменьшаем, если передан бит "0"

2. Когда встречаем уже инициализированный элемент массива - не меняем его и запоминаем разницу между позициями (текущая минус взятая от элемента массива) - это размер локальной максимальной последовательности.

3. Каждый раз, когда мы встречаем локальный максимум, сравниваем его с глобальным максимумом и обновляем, если последний меньше.

Например: последовательность битов 0,0,0,0,1,0,1

   initial array index is n
   set arr[n] = 0 (position)
     bit 0 -> index--
   set arr[n-1] = 1 
     bit 0 -> index--
   set arr[n-2] = 2
     bit 0 -> index--
   set arr[n-3] = 3
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [3,2] becomes abs. maximum
      will not overwrite arr[n-2]
     bit 0 -> index--
   arr[n-3] already contains 3 -> thus, local max seq is [4,3] is not abs. maximum
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [5,2] is abs. max

Таким образом, мы проходим весь массив битов только один раз. Решает ли это задачу?

input:
    n - number of bits
    a[n] - input bit-array

track_pos[2*n] = {0,};
ind = n;
/* start from position 1 since zero has
  meaning track_pos[x] is not initialized */
for (i = 1; i < n+1; i++) {
    if (track_pos[ind]) {
        seq_size = i - track_pos[ind];
        if (glob_seq_size < seq_size) {
            /* store as interm. result */
            glob_seq_size = seq_size;
            glob_pos_from = track_pos[ind];
            glob_pos_to   = i;
        }
    } else {
        track_pos[ind] = i;
    }

    if (a[i-1])
        ind++;
    else
        ind--;
}

output:
    glob_seq_size - length of maximum sequence
    glob_pos_from - start position of max sequence
    glob_pos_to   - end position of max sequence

Как было указано пользователем «R ..», строго говоря, решения нет, если вы не проигнорируете сложность пространства «log n». Далее я буду считать, что длина массива соответствует машинному регистру (например, 64-битному слову) и что машинный регистр имеет размер O (1).

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

Обозначения: массив имеет длину n , индексы отсчитываются от 0 до n-1 .

1. Первый проход: подсчитайте количество единиц ( c1 ) и нулей ( c0 ). Если c1 = c0 , то ваша максимальная подпоследовательность - это весь массив (конец алгоритма). В противном случае пусть d будет цифрой, которая встречается реже ( d = 0 , если c0 , в противном случае d = 1 ) .
2. Вычислить m = min (c0, c1) * 2 . Это размер искомой подпоследовательности.
3. Второй проход: просканируйте массив, чтобы найти индекс j первого появления d .
4. Вычислить k = max (j, n - m) . Подпоследовательность начинается с индекса k и имеет длину m .