# [C++] Typical DP N^2 solution and NLogN solution from GeekForGeek

• This is a classic problem and here is a DP solution for reference
Please note a NLogN solution can be found in the following link
Geek for Geek

``````class Solution {
public:
// There's a typical DP solution with O(N^2) Time and O(N) space
// DP[i] means the result ends at i
// So for dp[i], dp[i] is max(dp[j]+1), for all j < i and nums[j] < nums[i]
int lengthOfLIS(vector<int>& nums) {
const int size = nums.size();
if (size == 0) { return 0; }
vector<int> dp(size, 1);
int res = 1;
for (int i = 1; i < size; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j]+1);
}
}
res = max (res, dp[i]);
}
return res;
}
};
``````

• Also a C++ code base on geek for geek.

``````// NLogN solution from geek for geek
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) { return 0; }
vector<int> tail;  // keep tail value of each possible len
tail.push_back(nums[0]);
for (auto n : nums) {
if (n <= tail[0]) {
tail[0] = n;
} else if (n > tail.back()) { // large than the tail of current largest len
tail.push_back(n);
} else {  // find smallest one which is >= n
int left = 0;
int right = tail.size()-1;
int res = left;
while(left <= right) {
int mid = left + (right-left)/2;
if (tail[mid] >= n) {
res = mid;
right = mid-1;
} else { // tail[mid] < n
left = mid+1;
}
}
tail[res] = n;
}
}
return tail.size();
}``````

• Thank you very much for your nice solution. I am always lost when come to DP problems.

• Haha, I feared DP too in the past. Finally I found that once you got the DP formula, coding DP is just translation :-)

• me too... wondering is there any good practices (easy to hard) for us who is weak at DP problems.

• Yup. but the hard thing is to work out that formula...

• Really cool algorithm. In fact, the implementation of the binary search part can still be optimized a bit: using `left < right` as the terminating condition, we can get rid of `res` :-)

The code is as follows.

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> ends{nums[0]};
for (int num : nums) {
if (num > ends.back()) ends.push_back(num);
else {
int l = 0, r = ends.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (ends[m] < num) l = m + 1;
else r = m;
}
ends[r] = num;
}
}
return ends.size();
}
};
``````

There is a more clever implementation using `lower_bound` in this post, just 6-lines indeed.

• @LeoShi Would you like to have a look at here :-)

• Hey, your code is really cool, even come to details. Only record the last number of each array instead of whole array, use binary search in `else` case.

• @jianchao.li.fighter u got pretty good understanding

• @jianchao.li.fighter, the first `if` check `if (num < ends[0]) ends[0] = num;` can be merged into the `else` check, right?

• @caikehe Yeah, you're right! Thanks for your nice suggestions. I have updated my code now :-)

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