@koliane

Как найти максимум между двумя точками на дискретном графике?

дан график из точек. Нужно найти максимальное значение между любыми двумя точками (включая сами эти крайние точки).

Задача программная, поэтому к каждой точке можно добавить любую "метаинформацию", необходимую для вычислений. Т.е. данные можно подготовить, изначально добавив какую-то метаинформацию (если она нужна).
Хранить максимумы для всех комбинаций не могу, т.к. точек более миллиона, а комбинаций получится слишком много.

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

Пример:
c4dc3f7a54.jpg
Возьмем пару точек с порядковыми номерами {1,4}. Тут максимальное значение между ними = 4.
Возьмем пару точек с порядковыми номерами {4,5}. Тут максимальное значение между ними = 3.

Есть ли алгоритмы какие-то для этого? Можно ли вообще такое сделать?
  • Вопрос задан
  • 231 просмотр
Пригласить эксперта
Ответы на вопрос 3
gbg
@gbg
Любые ответы на любые вопросы
На дискретном графике максимум может быть только в узловой точке.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
В каждой точке хранить массив максимумов справа от неё. Потом перебором до конца интервала искать значение.
1: {1: 1, 2: 2, 3: 4}
2: {2: 2, 3: 4}
3: {3: 4}
4: {4: 0.3, 5: 3}
5: {5: 3}
6: {6: 1}

{1, 4} => Берём массив в точке 1, движемся по нему, ближайшее меньшее 4 - 3. Максимум 4.
Ответ написан
@Ritchi
Апроксимируйте полиномом второй или третьей степени и найдите максимум по производной. Посмотрите по сплайны.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы