[LeetCode]Longest Increasing Subsequence.cpp

如果用DP[i]表示以nums[i]结尾的LIS(Longest Increasing Subsequence)的长度，那么我们可以得到递推公式：

• DP[i] = max(DP[k]) + 1 (0 <= k < i &&  nums[i] > nums[k])

那么根据这个我们可以写出代码，时间复杂度O(n^2)，空间复杂度O(n):

	class Solution {
	public:
	int lengthOfLIS(vector<int>& nums) {
	int len = nums.size(), LIS = 1;
	if(!len)return 0;
	vector<int> dp(len, 1);
	for(int i = 1; i < len; ++i)
	{
	int localLen = 1;
	for(int j = 0; j < i; ++j)
	{
	if(nums[j] < nums[i])
	localLen = max(localLen, dp[j] + 1);
	}
	dp[i] = localLen;
	LIS = max(localLen, LIS);
	}
	return LIS;
	}
	};

view raw Longest Increasing Subsequence.cpp hosted with ❤ by GitHub

我们在Increasing Triplet Subsequence也提到过如何判断长度为k的IS(Increasing Subsequence)是否存在的方法。其更新DP的时候，由于DP本身就是sorted的，可以用binary search完成，这样时间复杂度可以到O(n * log n)，空间为O(len)，len为LIS的长度，代码如下;

	class Solution {
	public:
	int lengthOfLIS(vector<int>& nums) {
	int len = nums.size();
	if(!len)return 0;
	//minEnd[k] represents minimum ending number in subsequences with length k
	vector<int> minEnd;
	for(int i = 0; i < len; ++i)
	{
	if(minEnd.empty() || nums[i] > minEnd.back())
	minEnd.emplace_back(nums[i]);
	else if(nums[i] < minEnd.back())
	{
	int idx = binarySearch(minEnd, nums[i]);
	minEnd[idx] = nums[i];
	}
	}
	return minEnd.size();
	}
	private:
	int binarySearch(vector<int>& v, int target)
	{
	int lo = 0, hi = v.size() - 1;
	while(lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(v[mid] < target)
	lo = mid + 1;
	else if(v[mid] > target)
	hi = mid - 1;
	else
	return mid;
	}
	return lo;
	}
	};

view raw Longest Increasing Subsequence.cpp hosted with ❤ by GitHub