# C++ DP/Binary Search/O(nlogn) solution with simple explanation

• DP solution:

``````int lengthOfLIS(vector<int>& s)
{
if (s.size() < 2)
return s.size();
int ret = 0;
vector<int> dp(s.size(), 1);//dp[i] means the length of LIS of first i numbers (ended on number s[i]).
for (int i = 1; i < s.size(); ++i)
{
int t = 1;//The minimum length is 1
for (int j = 0; j < i; ++j)
{
if (s[j] < s[i])
t = max(t, dp[j] + 1);
}
dp[i] = t;
ret = max(ret, t);
}
return ret;
}
``````

============================================================
Binary Search solution:

``````int lengthOfLIS(vector<int>& s)
{
if (s.size() < 2)
return s.size();
int sz = s.size();
vector<int> v;
v.push_back(s[0]);
int i;
for (auto n : s)
{
if (n <= v[0])
v[0] = n;
else if (n>v.back())
v.push_back(n);
else //Use Binary Search to save time
{
int le = 0, ri = v.size() - 1;
while (le < ri)
{
int m = le + (ri - le) / 2;
if (n>v[m])
le = m + 1;
else
ri = m;
}
v[le] = n;
}
}
return v.size();
}
``````

============================================================
O(nlogn) solution:

``````int lengthOfLIS(vector<int>& s)
{
if (s.size() < 2)
return s.size();
vector<int> can(1, s[0]); //Candidate vector of end elements.
for (int i = 1; i < s.size(); ++i)
{
if (can[0] > s[i]) //If s[i] smaller than all elements in 'can', replace can[0] with s[i].
{
can[0] = s[i];
continue;
}
if (can[can.size() - 1] < s[i]) //If s[i] greater than all elements in 'can', add s[i].
{
can.push_back(s[i]);
continue;
}
int j = 0;
for (; can[j] < s[i]; ++j); //Find the position that s[i] is greater than preceding elements and smaller than subsequent elements.
can[j] = s[i];
}
return can.size();
}
``````

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