int binary_search(vector<int>& vec, int target) {
int low = 0, high = vec.size()  1;
while (low < high) {
int mid = (low + high) / 2;
if (target > vec[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
if (low == (int)vec.size()  1 && vec[low] < target) low++;
return low;
}
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i : nums) {
int idx = binary_search(dp, i);
if (idx > (int)dp.size()  1) {
dp.push_back(i);
} else {
dp[idx] = i;
}
}
return dp.size();
}
4ms C++ solution, O(nlgn) time complexity, using binary search


Hi man,
I appreciate your comment and correction!
You are a bit rude right there though! Why couldn't I tease you on the fact that your code needs extra O(N) space in the worst case. Not to mention that dp could allocate memory on the fly.
Should I vote it down here as you just did? Probably not.
Yours,

It could be an improvement to overwrite nums instead of allocating extra memory. On this problem, you're right. I'm considering what if we need to get the longest sequence instead of the length. Then we cannot overwrite 'nums'.
I vote up for good answers and vote down for bad ones. I feel sorry if that offended you. I would 't mind receving a vote down if it's really awful. I can learn from it. And I would learn it by heart and avoid programming or making mistakes like that.