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


  • 1

    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();
    }
    

Log in to reply
 

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