# 5 lines O(n log n) C++ solution

• Like most ACed solutions, we can use Binary Search to speed up the original O(n^2) DP solution.

``````// C++ Code
int lengthOfLIS(vector<int>& nums) {
vector<int> ans;
for (int a : nums)
if (ans.size() == 0 || a > ans.back()) ans.push_back(a);
else *lower_bound(ans.begin(), ans.end(), a) = a;
return ans.size();
}
``````

Runtime = O(n log n).

• Very tricky!

• Yeah, the trick here is that *lower_bound() can be used as an lvalue.

• This is a beautiful solution!

ans[i] maintains the smallest ending integer, among all ascending subsequence with length of i. Once I realize this, the algorithm becomes crystally clear.

• You are right, and I am glad you like it. :)

• Do note that if, as a followup, you were asked to return the actual vector containing the minimum subsequence, you can't just return ans:

e.g.

``````2 3 7 9 5
``````

ans will replace 7 with 5 and thus return

``````2 3 5 9
``````

whereas the correct solution is

``````2 3 7 9
``````

however, the lengths of the optimal solution and our current solution will be the same!

• cool algorithm

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.