longest increasing subsequence(O(nlogn))
Let’s first look at the n^2 algorithm: Now the improvement happens at the second loop, basically, you can improve the speed by using binary search. Besides the array dp[], let’s have another array c[], c is pretty special, c[i] means: the minimum value of the last element of the longest increasing sequence whose length is … Read more