CP-algorithms has a wrong proof

Problems and Contests
#1

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?

1 Like
#2

It’s mentioned in the LIS module.

#3

You are correct. The statement in the proof that “the minimum number of required colors is equal to the length of the longest increasing subsequence” is incorrect.

A correct proof for the statement “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” is as follows:

Let’s consider an array of n numbers, a[0…n−1].

We can colorize the numbers in the following way:

Start with the first number (a[0]) and color it with color 1.
For each subsequent number a[i], if it is greater than any of the previously colored numbers (a[0], a[1], …, a[i-1]), then color it with a new color j, where j is one greater than the maximum color used so far.
If a[i] is not greater than any of the previously colored numbers, then color it with the same color as the smallest number among the previously colored numbers that it is greater than.
Repeat this process for all numbers in the array, from left to right.
Since we are coloring the numbers in a non-increasing subsequence with the same color, and we are always using the smallest available color for a number that is not greater than any previously colored numbers, it is guaranteed that each color will form a non-increasing subsequence.

The minimum number of required colors will be equal to the length of the longest increasing subsequence, because for each increasing subsequence, we will need a new color, and the length of the longest increasing subsequence will be the maximum number of colors used.

Therefore, the correct statement should be “the minimum number of required colors is equal to the length of the longest increasing subsequence”.

The example sequence you provided (5 4 3 1 2 0) does not contradict the correct proof. The correct proof shows that each color forms a non-increasing subsequence, not a strictly decreasing subsequence. In the example sequence, the numbers 5, 4, 3, and 1 will be colored with the same color, forming a non-increasing subsequence. Similarly, the numbers 2 and 0 will be colored with the same color, forming another non-increasing subsequence. Reference of the answer from here.