USACO - Динамическое программирование - Максимально уменьшающаяся подпоследовательность

Question

Я перепутал с кодом, который написан в разделе динамического программирования TEXT Тренинга USACO о классической задаче (Нахождение максимально убывающей подпоследовательности). Это ссылка на статью. Пожалуйста, помогите мне получить это!

Вот код:

 1  #include <stdio.h>
 2  #define MAXN 200000
 3  main () {
 4      FILE *in, *out;
 5      long num[MAXN], bestrun[MAXN];
 6      long n, i, j, highestrun = 0;
 7      in = fopen ("input.txt", "r");
 8      out = fopen ("output.txt", "w");
 9      fscanf(in, "%ld", &n);
10      for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]);
11      bestrun[0] = num[n-1];
12      highestrun = 1;
13      for (i = n-1-1; i >= 0; i--) {
14          if (num[i] < bestrun[0]) {
15            bestrun[0] = num[i];
16            continue;
17        }
18        for (j = highestrun - 1; j >= 0; j--) {
19            if (num[i] > bestrun[j]) {
20                if (j == highestrun - 1 || num[i] < bestrun[j+1]){
21                    bestrun[++j] = num[i];
22                    if (j == highestrun) highestrun++;
23                    break;
24                }
25            }
26        }
27      }
28      printf("best is %d\n", highestrun);
29      exit(0);
30  }

У меня есть 3 проблемы с этим:

1) Что именно делают строки 14-17? Например, для последовательности 10, 2, 8, 9, 4, 6, 3 результат этого кода равен 4, но его подпоследовательность равна 10, 8, 4, 2, что неверно, поскольку элемент 2 в исходной последовательности имеет вид до 8 и 4, но в результирующей подпоследовательности - после 8 и 4!

2) Рассмотрим последовательность 5, 10, 8, 9, 4, 6, 3. Согласно приведенному выше коду, длина максимально убывающей подпоследовательности равна 4, а эта подпоследовательность равна 10, 5, 4, 3. Но в этой подпоследовательности противоположно оригинальной последовательности 5 после 10.

3) нужно ли проверять num[i] < bestrun[j+1] состояние во внутреннем цикле? Я думаю, что до этого num[i] > bestrun[j] состояние.

Я жду от вас полезных ответов.
Спасибо за вашу помощь!

Answer 1

1) bestrun[i] отслеживает наименьшее целое число, которое является началом самой длинной убывающей подпоследовательности длины i + 1. Поэтому, если вы встретите значение, которое меньше вашего текущего bestrun[0]хочешь изменить bestrun[0] к этому значению, поскольку это будет наименьшая убывающая подпоследовательность длины 1.

2) Я не совсем уверен, что вы спрашиваете. Если вам интересно, что происходит, когда вы переворачиваете последовательность, вы можете вместо этого запустить алгоритм с самой длинной возрастающей подпоследовательностью, чтобы получить тот же результат.

3) Да, это кажется излишним, так как bestrun должно быть нерастущим. Фактически, некоторые реализации самой длинной увеличивающейся / убывающей подпоследовательности используют этот факт для улучшения времени выполнения до O(n log n), выполняя бинарный поиск, чтобы найти самую высокую j такой, что num[i] больше чем bestrun[j],