@BAF1

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

У меня есть массив чисел, мне нужно разбить его на группы так, чтобы каждая из них была длины от l до r (менять порядок чисел (сортировать) нельзя) и, чтобы суммарная разница между максимальным и минимальным числом была максимальна.
Если разбиение возможно несколькими способами, то вывести любой из них

Например, есть массив [98, 99, 98, 100, 98, 99, 98]; l = 2; r = 4. В ответе будет разбиение на 3 подмассива: [98, 99] [98, 100] [98, 99, 98]. Суммарная разница здесь будет 4.

Я вот думаю, есть ли тут динамическое программирование?
  • Вопрос задан
  • 151 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность.

Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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