Есть ли конкретный алгоритм для такого рода проблем?

Question

Я столкнулся с парой подобных проблем, когда в наборе есть пара предметов e _i = {w _i , h _i } для i=0..n, вы должны найти самую длинную серию, такую ​​что w _m > w _{m + 1} и h _м > ч _{м + 1} для каждого последующего значения m.Звучит знакомо?Кто-нибудь может указать конкретный алгоритм, который может иметь дело с аналогичными проблемами?

Answer 1

Один из способов сделать это - построить ориентированный ациклический граф, в котором есть узел для каждого ei и ребро от ei до ej, если ej> ei (в том смысле, в котором вы говорите выше). Затем найдите самый длинный путь в этом DAG .

Answer 2

Вы ищете самую длинную увеличивающуюся подпоследовательность, поэтому сортировка по терпению , вероятно, является подходящим вариантом.

При реализации этого вам нужно написать свой собственный метод Comparatorэто говорит e_i < e_j тогда и только тогда, когда w_i < w_j и h_i < h_j.Тот факт, что у вас есть частичный заказ вместо общего, не меняет алгоритм.