USACO -动态规划-最大递减子序列

Question

我对USACO培训中关于一个经典问题(寻找最大递减子序列)的文本动态编程部分中编写的代码感到困惑。这是Article Link。请帮我拿一下！

代码如下：

 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应该是不增加的。事实上，一些最长递增/递减子序列的实现利用了这一事实，通过执行二进制搜索来找到最高的j，使得num[i]大于bestrun[j]，从而将运行时间提高到O( n )。