Самый длинный вложенный массив во вращающемся массиве

Question

Есть ли способ найти самый длинный подмассив из 1 в журнале (n) времени?

пример:

1. 110011111000 - тогда на выходе будет 5 (от 5 до 10)

2. 1110011101 - выходное значение здесь равно 3, но после вращения 1 массив становится 111100111, а выходное значение равно 4.

3. 001111 - выходное значение здесь равно 4 от 3 до 6, но после вращения оно становится 3 от 4 до 6

Примечание: я нашел самую длинную длину подмассива в O (n) перед вращением. Как я могу улучшить решение после ротации, если у меня есть прошлые результаты?

Answer 1

Вы можете выполнить следующие шаги:

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

Я предполагаю, что вы знаете, как получить максимальный индекс подмассива и считать в O (n). В дополнение к этому вам нужно будет найти второй по величине подмассив (можно сделать в том же цикле).

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

При вращении массива есть 3 варианта:

1. Ничего не меняется
2. Создан большой подмассив
3. Текущие самые большие разрывы подмассива

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

Например, предположим, у вас есть массив: 1110011101 (как ваш пример), и у вас есть max = 3 и maxIndex = 5. После запуска функции getZeroIndexs вы также знаете, что firstZeroIndex = 3 и lastZeroIndex = 8.

Как будет выглядеть наша переменная после вращения?

max = 3
maxIndex = 6
firstZeroIndex = 4 // this will increase as long as the lastZeroIndex different then the array size
lastZeroIndex = 9 //this will go up till array.size - when it those you need to loop again till you find last

В этом случае первый индекс перемещается на 4, что делает его больше, чем max -> max = 4 и maxIndex = 0.

Теперь ваш массив: 1111001110, поэтому lastZeroIndex = 9 как размер массива, так что следующий поворот даст:

max = 4
maxIndex = 1
firstZeroIndex = 0 
lastZeroIndex = ? // here you need to loop from the end of your array till you get 0 -> O(k) in total complexity, all the run together will be O(n)  

Надеюсь, это ясно, если не стесняйтесь спрашивать!

Answer 2

Нет, потому что вы должны знать каждое буквенное значение, чтобы считать 1 с, что как минимум равно O (n).