The bottleneck: for each element, we scan all previous elements. Can we do better? observation: maintain an array where is the smallest ending element of all increasing subsequences of length . When you see a new element :
If is larger than all elements in , append it (extends the longest subsequence).
Otherwise, find the smallest element in that is and replace it with . Why replace? A smaller ending value gives more room to extend later. The length of is your answer.