In the last section of cp-algorithm longest increasing subsequence, it proves that
For a given array with n numbers a[0…n−1] we have to colorize the numbers in the smallest number of colors so that each color forms a non-increasing subsequence.
To solve this, we notice that the minimum number of required colors is equal to the length of the longest increasing subsequence.
However, I think this sentence in the proof is wrong.
After a finite number of steps we have y subsequences, and their starting numbers will form an increasing subsequence of length y
Hack:
sequence: 5 4 3 1 2 0
sequence: 5 4 3 1 2 0
sequence: 5 4 3 1 2 0
sequence: 5 4 3 1 2 0
.
.
.
this goes on forever.
Can someone give me the correct proof?