[LeetCode]Increasing Triplet Subsequence

想假设寻找是否存在长度为2的IS(increasing subsequence)怎么做。从左向右扫，维护最小值，然后看当前数是否比维护的最小值大，如果是的话我们就验证数组中有长度为2的IS。如果数组中存在IS，这个方法一定能够验证，因为假设存在递增序列n[i], n[j]，假设n[i]不是从n[0]到n[j]的最小值，我们一定找到了更小的从而验证了n[j]结尾的递增序列。如果n[i]是最小值，那我们就找到了递增序列。那么对于长度为3的IS，我们依次类推，DP[i]表示长度为i的IS结尾的最小值，如果DP[i]不存在则代表不存在长度为i的IS，因为，我们找到了长度为i - 1的IS的结尾的最小值m，m在每一时刻可能不相同，但是我们在数组的任何位置都无法找到大于当前m的值，也就是说数组的任何位置都不可能为长度为i的IS的结尾，所以其不存在。那么我们如何更新DP呢，如果当前数n比DP的最后一个数e（当前最长IS结尾的最小数）大，则我们可以找到更长的IS，我们将n加入DP的末尾，否则我们将DP当中大于n的最小值更新为n，代表我们找到了更小的某长度的IS的结尾。很显然对于这一题，我们只需要判断DP在某一时间size是否为3，代表存在ITS，时间复杂度O(n)，常数空间，代码如下：

	class Solution {
	public:
	bool increasingTriplet(vector<int>& nums) {
	int len = nums.size(), first = INT_MAX, second = INT_MAX;
	for(auto& num : nums)
	{
	if(num < first)
	first = num;
	else if(num > first && num < second)
	second = num;
	else if(num > second)
	return true;
	}
	return false;
	}
	};

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