I've confused with the code that is written in the TEXT Dynamic Programming section of USACO Training about a classical problem (Finding Maximum Decreasing Subsequence). This is Article Link. Please help me to get it!
Here's the code:
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 }
I have 3 problems with it:
1) What exactly lines 14-17 do? For example for the sequence 10, 2, 8, 9, 4, 6, 3 , the result of the that code is 4 but it's subsequence is 10, 8, 4, 2 that it's wrong, because the element 2 in original sequence is before 8 and 4 but in the resulting subsequence is after 8 and 4!
2) Consider the sequence 5, 10, 8, 9, 4, 6, 3. According to above code, the length of the maximum decreasing subsequence is 4 and this subsequence is 10, 5, 4, 3. But in this subsequence opposite of the original sequence 5 is after 10.
3) Is it necessary to check num[i] < bestrun[j+1] condition in inner loop? I think it's satisfied before by num[i] > bestrun[j] condition.
I'm waiting for you helpful answers.
Thanks for your help!
(My English is broken, so, maybe I can't express my thoughts very well)
I want to tell you that the element in array "bestrun" is not the really "Maximum Decreasing Subsequence",they are not sorted by appears order.
Before answering your questions, I want to make the means of bestrun[i] clear.
You must know that the procedure is from right to left to find a maximum increasing subsequence.
Bestrun[i] means a subsequence( length is i )'s reachable minimum element(at the i th position),
(maybe i don't explain clearly, but i think you can understand it better by debuging the program)
if we have the information in "bestrun ",we can refresh the answer easier and efficiently. We even can use it to make the program faster.(from O(n^2) to O(nlogn))
Now,I would answer your problems,
1)The function of the lines 14-17 is to refresh the bestrun[0], (the main reason is that the bestrun[0] can't be freshed in the loop) if the element is the minimum then it must be an end of a Maximum Decreasing Subsequence, if another element after it is exactly bigger than it ,they may make the subsequence longer.
2)As the means of the array, the real Maximum Decreasing Subsequence is not stored in bestrun.
3)The check is not necessary to be in inner loop,but if it is in inner loop,it may run faster(because the break).
I hope that my explain can help you.
Thanks for your great answer!
ahan. You mean, it just stores the length of the maximum decreasing subsequence of the original sequence. Yeah?
I've been thinking that bestrun array stores elements of maximum decreasing subsequence.
But about question 3: How this condition makes running faster? I don't know exactly why how that condition makes running faster! What about changing inner loop to below?
Could you explain it?
Thank you!
It not directly stores the information of the length, highestrun stores the length.
In the loop, bestrun[j] means until now the minimum tail element of a possible subsequence whose length is j.
About the program's running speed, I'm sorry, maybe what I said is wrong,(because I understand your meaning wrongly) but that it's able to be faster is a true thing.
And I think that your changed inner loop is right.(...But I have to say I'm learning PASCAL and I can't understand C or C++ very well.)
Although I say so much above, I still think I can't express my thoughts accurately, so I think I should give an example.
For example for the sequence you mentioned 10, 2, 8, 9, 4, 6, 3, let's imitate the program how to run.
At first, bestrun={3}
highestrun=1
it means that we can find a sequence whose length is 1 and its minimum tail element is 3.
then i=6
bestrun={3, 6}
highestrun=2
it means that we can also find a sequence whose length is 2 and its minimum tail element is 6.
(the sequence is 3, 6)
then i=5
bestrun={3, 4}
highestrun=2
it means that we can also find a sequence whose length is 2 and its minimum tail element is 4.
(the sequence is 3, 4)
then i=4
bestrun={3, 4, 9}
highestrun=3
it means that we can find a sequence whose length is 3 and its minimum tail element is 9.
(the sequence can be 3, 4, 9 or 3, 6, 9)
then i=3
bestrun={3, 4, 8}
highestrun=3
it means that we can find a sequence whose length is 3 and its minimum tail element is 8.
(the sequence can be 3, 4, 8 or 3, 6, 8)
then i=2
bestrun={2, 4, 8}
highestrun=3
it means that now we can find a new sequence whose length is 1 and its minimum tail element is 2.
then i=1
bestrun={2, 4, 8, 10}
highestrun=4
it means that we can find a sequence whose length is 4 and its minimum tail element is 10. (one of the sequences can be 3, 4, 8, 10, now there are many sequences whose length is 4.)
At last,
bestrun={2, 4, 8, 10}
(I think now you could know, this is not a real subsequence) highestrun=4
The principle of the algorithm is that we should let a sequence's tail element be smaller and it will be better and easier to make the sequence longer in the next procedure.
I hope my explain can help you understand it.
WOW...Thanks a lot for your perfect explanation! you're great ;) I get it completely...
Thanks for your help, My Friend!
You are welcome.