Алгоритм - Минимум Больше чем размер

Question

У меня есть проблема с этим:

Мы имеем целочисленный массив (размер п) [x_1,x_2,...,x_n]

Мы должны найти самую длинную общую часть [x_i,x_i+1,...,x_j] что минимум (x_i,x_i+1,...,x_j) >= j-i+1 Fe [2,2,1,4,3,3,1] -> 3 (самая длинная правильная часть 4,3,3)

Я не могу понять, как сократить время ниже O(n^2) (Проверка каждого отдельного сегмента) Моя вторая мысль была: Каждое значение x_k равно «Len gth range ", что эта часть может иметь, если есть меньшее число, тогда мы меняем« диапазон длин »(тем временем подсчитывая, как долго этот сегмент), но я не знаю, что делать, если мы получим большие цифры

(я был бы очень благодарен за любую помощь - там, наверное, другое простое решение, но я не вижу)

Answer 1

метод Caterpillar, O (N), предполагая, что все целые числа будут положительными:

• Поместите левый и правый указатель на первое число, а ваш минимум = этот номер. Длина = 1
• Продвиньте правый указатель на один, проверьте состояние (вы знаете, если есть новый минимум очень легко, и вы знаете длину + = 1)
• Если вы не можете продвинуть правый указатель, не нарушая условие, продвиньте левый указатель и обновите свои значения.
• Если вы не можете продвинуть левый указатель, вы нашли раздел, удовлетворяющий условию. Обратите внимание на его длину и начинайте новый раздел таким же образом, по следующему индексу.

Пример для вас:

[2,2,1,4,3,3,1] 
[2] <- The first 2 
[2,2] <- Moved the right 
[2] <- Moved the left, both R and L are pointing at the second 2 
<-Can't move either, note max length and indices from previous run. 
[1] <- Starting again 
<-Can't move either 
[4] <- Starting again 
[4,3] <- Right 
[4,3,3] <- Right (New max length and indices noted) 
[3,3] <- Left. Doesn't improve the max 
[3] <- Left again. 
<- Can't move either, note max and indices, in this case overwrite length 
[1] <-Start again 
<- end of loop, check global max length, output 

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

Я думаю, этого должно быть достаточно, чтобы вы могли написать алгоритм на любом выбранном вами языке. Следите за условием конца цикла, потому что вам нужно проверить глобальную максимальную длину, если у вас закончится массив.