I am having trouble understanding the nlogn algorithm for solving the LIS problem. I have implemented the algorithm given here on page number 6. Link to CPP implementation. I think it's only checking the subsequence starting at index
0 so how is this algorithm correct? Or is my implementation wrong? Someone please help prove the correctness of this algorithm. Thanks.