Всем привет!

Нужен алгоритм для такой задачи.

1. Есть набор {a[k], k=0..N} целых чисел, таких что
— a[0] = 0
— для любых k=0..N-1 верно a[k] < a[k+1]
(отсортированный набор целых чисел, первое число ноль ).

2. Для целого числа C > 0 определим целочисленную функцию на наборе k=0..N :

F(k, C) = max { m | k+m <= N, a[k+m] <= a[k]+C }

(количество чисел, покрытых интервалом a[k]..a[k]+C )


Нужен алгоритм для поиска индекса(-ов) k, доставляющего максимум функции F(k, C) для заданного C.

RB>Нужен алгоритм для поиска индекса(-ов) k, доставляющего максимум функции F(k, C) для заданного C.

сколько раз будет выполняться этот поиск для разных C?

Здравствуйте, dilmah, Вы писали:

D>сколько раз будет выполняться этот поиск для разных C?

Один раз.
Потом набор чисел меняется, меняется и значение C.

Интересует что-нить более эффективное прямого перебора.
Если есть несколько k, желательно найти все.

вспомнил, мне такую задачу (в другой формулировке) спрашивали на собеседовании в рамблер.

ну идешь двумя итераторами, левым итератором всегда вперед, правым туда-сюда и ищешь максимум..

Здравствуйте, dilmah, Вы писали:

D>ну идешь двумя итераторами, левым итератором всегда вперед, правым туда-сюда и ищешь максимум..

Ну, перебор очевиден.
Может есть что-то более эффективное?
Например, "правый итератор" двигать более эффективно?
Возможно, используя результаты сканирования на предыдущем значении "левого итератора"...



ЗЫ
Чилийцы молодцы, не сникли.
Но все равно сольют...

D>>ну идешь двумя итераторами, левым итератором всегда вперед, правым туда-сюда и ищешь максимум..

RB>Ну, перебор очевиден.
RB>Может есть что-то более эффективное?
RB>Например, "правый итератор" двигать более эффективно?

это и так линейное решение. совсем тупой перебор давал бы квадратичное.

Здравствуйте, dilmah, Вы писали:

D>>>ну идешь двумя итераторами, левым итератором всегда вперед, правым туда-сюда и ищешь максимум..

D>это и так линейное решение.

Точно, правый итератор можно двигать только вперед...
Спасибо!