The solution is building a ladder for numbers, with level number labels the max sequence for all numbers on that level;

when a new number comes in, compare it with the smallest number in each level--starting from the highest level, if larger than the (smallest) number in that level, the new number is insert into level+1

else compare with the smallest number in second highest level ...

e.g. [10, 9, 2, 5, 3, 7, 101, 18]

level: numbers

4: 101, **18**

3: **7**

2: 5, **3**

1: 10, 9, **2**

Since we only use the **smallest number** in each level, we do not need save the others, an extra vector<int> of size m(=max level) would be enough

```
int lengthOfLIS(vector<int>& nums) {
vector<int> ladder(1);
if(nums.empty()) return 0;
ladder[0]=nums[0];
for(int i=1; i<nums.size(); ++i){
int m=int(ladder.size());
bool foundless=false;
for(int j=m-1;j>=0;--j){
if(nums[i] > ladder[j]){
if(j+1==ladder.size()){
ladder.push_back(nums[i]);
}
else{
ladder[j+1]=min(ladder[j+1],nums[i]);
}
foundless=true;
break;
}
}
if(!foundless) ladder[0]=min(ladder[0],nums[i]);
}
return ladder.size();
}
```