Что не так с алгоритмом для поиска наибольшей неубывающей подпоследовательности?

Question

[Ашот Такиев]

Добрый день.

У меня возникли проблемы с задачей на нахождение наибольшей неубывающей последовательности за время O(nlogn). Необходимо вычислить длину и восстановить индексы элементов подпоследовательности.
Вроде все просто, завести два массива (один для хранения текущей подпоследовательности, а в другой записывать индексы добавленных элементов). Первый массив заполняется какими-то большими значениями, а самый левый элемент задается самым минимальным. И с помощью двоичного поиска мы находим, куда именно нужно вставлять искомый элемент.

Получился такой вот код:

template <typename Cont>
Cont lis_bottom_up(const Cont& numbers) {
  const auto len = numbers.size();
  vector<int> d(len + 1);
  vector<int> prev(len, no_prev);
  d.front()= inf_min;
  fill(d.begin() + 1, d.end(), inf_max);

  for (auto i = 0; i < len; ++i) {
    auto j = distance(d.begin(), upper_bound(d.begin(), d.end(), numbers[i]));
    if (d[j - 1] <= numbers[i] && numbers[i] < d[j]) {
      d[j] = numbers[i];
      prev[j - 1] = i;
    }
  }
  auto res = build_answer(prev);

  return res;
}

Но что-то идет не так и, например для последовательности:
2 4 4 3 5
Получается подпоследовательность вида:
2 3 4 5
Все из-за того, что на 4 шаге, когда мы встречаем 3, upper_bound выдает элемент с индексом 2 (d[2] = 4; d[1] = 2; d[0] = inf_min) и по текущим условиям ничего не мешает вставить этот элемент между ними.
Все это из-за неверных условий, но как их поменять, пока не понял.
Буду очень признателен, если кто-нибудь направит мою мысль в нужную сторону.

Answer 1

[Mrrl]

В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
[1,2,7,8,9]
[1,2,5,6]
[1,2,3]
[1,2]
[1]
Любая из этих последовательностей может быть началом правильного ответа.
Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
Для примера [1,2,7,8,9,5,6,3] получаем
d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
(значение -1 используется для обозначения ситуации "нет такого индекса").

Comments

[Ашот Такиев]

Спасибо за ответ. Только я не очень понимаю, каким образом у Вас заполняются массивы d и prev.
Насколько я понял, изначально d заполнен как-то так d = [-1, inf, inf..... inf], prev также. Для 1 мы используем двоичный поиск по d и видим, что можем вставить элемент на 1 позицию. Записываем в d[1] = 0, prev[j - 1] = -1, так как предыдущего нет. Для 2 видим, что можно вставить её на 2 позицию, обновляем d и prev соответственно. Но дальше я теряю нить рассуждений, так как не понимаю, что делать дальше. У вас в массиве d хранятся {-1,0,1,7,6,4,-1,-1,-1,...}, но это не является правильной подпоследовательностью, т. к. элемент с индексом 7 < чем элемент с индексом 6.

[Mrrl]

Ашот Такиев: В начале d={-1,-1,-1,...} - ни одной последовательности у нас нет.
Приходит элемент с индексом 0, равный 1. Он образует последовательность длины 1, предыдущего элемента у него нет. Поэтому у нас есть последовательность длины 1, кончающаяся на элементе с индексом 0 (d[1]=0), и prev[0]=-1.
Приходит элемент с индексом 1, равный 2. Последовательность длины 1 из него делать неэффективно (поскольку у нас уже есть последовательность с меньшим последним элементом), но мы можем добавить его к имеющейся последовательности, и получить последовательность длины 2: d[2]=1, prev[1]=0 (элемент с индексом 1 идёт после элемента с индексом 0).
Аналогично обрабатываем 7,8 и 9: d[3]=2, prev[2]=1; d[4]=3, prev[3]=2; d[5]=4,prev[4]=3.
Приходит 5 (элемент с индексом 5). Его мы можем вставить после двойки, получив лучшую последовательность длины 3: d[3]=5, prev[5]=1. Дальше получится d[4]=6, prev[6]=5 и d[3]=7, prev[7]=1.
Чтобы построить по массивам d и prev ответ, надо ещё поработать. Начать с элемента d[5]=4 (самая длинная последовательность), потом взять prev[4]=3, prev[3]=2, prev[2]=1, prev[1]=0, prev[0]=-1. Это (кроме последнего числа) индексы ответа, записанные в обратном порядке. Берём элементы исходного массива по этим индексам: 1,2,3,8,9 - они и дадут ответ.

[Ашот Такиев]

Mrrl: Дошло, спасибо.)