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?