поиск по массиву

[mihatel]

Вопрос: есть массив натуральных чисел. Представим себе, что на плоскости он задает некоторую криволинейную трапецию. В этом массиве надо найти прямоугольник максимальной площади, вписанный в эту "трапецию". Двойной цикл не подходит: надо быстрее.

[photon]

Не совсем понятно условие. Массив пар натуральных чисел? Они заполняют эту "трапецию" или определяют его границу? Ориентация "трапеции" произвольная? Исходный массив как-то упорядочен?

[mihatel]

photon в сообщении #1434847 писал(а):

Не совсем понятно условие. Массив пар натуральных чисел? Они заполняют эту "трапецию" или определяют его границу? Ориентация "трапеции" произвольная? Исходный массив как-то упорядочен?

Уточняю. Задан обыкновенный одномерный неупорядоченный статический массив. Значения в ячейках определяют значения функции одной переменной величины - индекса массива. Ось абсцисс и функция, таким образом определенная, ограничивают криволинейную трапецию на отрезке от единицы до последнего индекса массива. И в эту трапецию надо вписать прямоугольник, то есть найти два индекса массива, таких что произведение модуля их разности на минимальное значение элемента массива в интервале между этими индексами было бы максимальным среди всех возможных пар индексов.

[arseniiv]

Напрашивается идти одновременно с обоих концов и что-то там запоминать о лучшем прямоугольнике, и сдвигаться в сторону центра то с одной, то с другой стороны в зависимости от того, где будет лучше дельта площади. Доказывать корректность придётся, конечно, чтобы убедиться, что оно работает всегда, а то вдруг нет. ← UPD: это совсем не про криволинейную.

[Sender]

arseniiv в сообщении #1434940 писал(а):

сдвигаться в сторону центра то с одной, то с другой стороны

А вдруг в центре сталактит, упирающийся в пол?
Кстати, всё, что ниже него, входит во все возможные прямоугольники. Это даёт идею решения: выбираем самый низкий("длинный") сталактит, поднимаем дно до него, вся пещера разбивается на две, их рассматриваем по отдельности таким же образом.

[arseniiv]

А, mea culpa, я пропустил «криволинейную трапецию» в условии. Подумал: о как хорошо, просто трапеция. Зачёркиваю.

[Mihaylo]

Преобразуем массив в двумерный список (значение, индекс), при чем создаем две копии списка. В первой копии списка будут храниться потенциальные координаты левой верхней точки прямоугольника, во второй копии - верхней правой точки прямоугольника. Далее бегаем по спискам и отбрасываем заведомо негодные координаты. Тут уже можно ухищряться. Самое простое, что можно придумать: сравниваем попарно две соседние точки и отбрасываем менее выгодную, при необходимости копируем меньшее значение.
После первого прохода списки похудеют вдвое.
Можно придумать, что делать дальше... Самое простое - перебор влоб.

Еще предложение - сделать списки не двумерные, а трехмерные. Третье значение - обнаруженная прямоугольная площадь слева/справа.

[photon]

Была такая задача https://www.hackerrank.com/interview/interview-preparation-kit/stacks-queues/challenges - задача "Largest Rectangle". Там придется залогиниться, чтобы посмотреть раздел Editorial, в котором разобрано решение. Не заглядывал, но насколько я знаю, решается при помощи стека за линейное время (идем по массиву и пока значения растут - пушим в стек, когда уменьшаются - вынимаем и считаем площадь).

[realeugene]

Когда координата растёт, это "открывает" новые возможные прямоугольники. Когда координата падает, это "закрывает" возможные прямоугольники. Организуем стек, глубина которого не превышает длину массива. Проходим по массиву один раз. При увеличении текущей координаты добавляем в стек координату левого верхнего угла кандидата. При повторении не делаем ничего. При уменьшении извлекаем левые углы всех закрытых прямоугольников, оставляя один глобально лучший, и, возможно, помещаем в стек один новый левый угол-кандидат.

[Munin]

Сканируйте трапецию горизонтальной линией.

А, это решение $\mathcal{O}(n\log n),$ а тут придумали лучше.

[mihatel]

realeugene в сообщении #1434971 писал(а):

Когда координата растёт, это "открывает" новые возможные прямоугольники. Когда координата падает, это "закрывает" возможные прямоугольники. Организуем стек, глубина которого не превышает длину массива. Проходим по массиву один раз. При увеличении текущей координаты добавляем в стек координату левого верхнего угла кандидата. При повторении не делаем ничего. При уменьшении извлекаем левые углы всех закрытых прямоугольников, оставляя один глобально лучший, и, возможно, помещаем в стек один новый левый угол-кандидат.

Спасибо!

[_Ivana]

Ссылка на разбор (наверное) этой задачи с примером кота, который проходит все тесты на 2 сайтах

[realeugene]

(OMG)

_Ivana в сообщении #1435081 писал(а):

Ссылка на разбор (наверное) этой задачи с примером кота, который проходит все тесты на 2 сайтах

if (hln > hrn) нужно было, тоже, в одну строчку написать. Для сохранения стиля породы кота.