I looked at the following website describing the longest increasing subsequnce algorithm: https://www.fyears.org/2016/12/LIS.html

In the section "how to reconstruct the subsequence?", it says that "We should pay attention that the dp in the end is NOT the LIS."

Somehow I don't see how dp is not LIS?

We know that dp is sorted and that it contains as many entries modified by the algorithm as the length of the LIS. An element at index i cannot be equal to an element at i-1, since for every index dp[i] contains the smallest possible ending value in all increasing subsequences with length i 1. So, if there is a subsequence of length i 1, this implies that there is also a subsequence of length i, which consequently must end at a smaller value, right?

CodePudding user response：

LIS is a subsequence (fixed order of elements), but DP array isn't saving elements order. Check on array [2, 3, 1]. DP will be [1, 3] after all iterations, but [1, 3] isn't the subsequence of the initial array.