USACO - 動態規劃 - 最大遞減子序列

Question

我對在USACO Training的TEXT Dynamic Programming部分編寫的關於經典問題（查找最大遞減子序列）的代碼感到困惑。這是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應該是nonincreasing。事實上，最長增加/減少子序列的一些實現利用這個事實，通過進行二進制搜索來找到最高的j，使得num[i]大於bestrun[j]，以將運行時間提高到O（nlogn）。