题目：Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists 

i, j, k 

such that 

arr[i] < 

arr[j] < 

arr[k] given 0 ≤ 

i < 

j < 

k ≤ 

n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:

Given [1, 2, 3, 4, 5],

return true.

Given [5, 4, 3, 2, 1],

return false.

题目：给定一个数组中找到是否有长度为3的递增序列，是返回true。

注意：序列只需要递增不一定需要连续。

也就是说只需要在下标递增的情况下，找到三个逐渐增大的数即可。

思路：

因为只需要找三个数，所以简单思考，只需要记住两个递增的数，然后遇到第三个数，该数大于这两个数就可以了。

同时不忘了，当遇到较小的数的时候适当更新前两个数。那么什么时候更新前两个数呢？

方便描述，我假设3个递增的数中最小的是smaller，中间的是larger，最大的是max。

初始化，smaller=A[0]，larger=INT_MAX；

当遇到smaller< N <larger的数时，就要更新larger=N；

当遇到N<smaller的数时，就要更新smaller=N；这样才能进一步更新larger，此时还没有更新larger，如果N不是有效的结果由于最终只比较larger来得出判断结果，所以也没有影响。

当遇到N>larger时，就得出true的结果，直接返回。

 

/*F(i)表示i处的升序的长度F(i) = max{nums[i] > nums[j] + F(j)}但是由于只需要判断长度为3的增序子序列，所以，只需要记录前面的最小值smaller，和增序长度为2的最小值larger就可以知道当前元素的增序子序列长度。当当前元素cur > larger时，长度变为3，即存在长度为3的增序子序列；当cur < larger时，又分为cur > smaller时，当前元素的长度是2，且更新larger；或cur < smaller时，当前元素长度为1，且更新smaller；*/bool LeetCode::increasingTriplet(vector
     
      & nums){	if (nums.size() < 3)return false;	//length记录增序子序列长度，smaller记录直到当前位置的最小值，larger记录length=1时的最小值	int length = 0, smaller = nums[0], larger = INT_MAX;	for (size_t i = 1; i < nums.size(); ++i){		if (nums[i] > larger)return true;//存在		else if (nums[i] < larger){			if (nums[i] > smaller){				larger = nums[i];//更新larger				length = 1;//长度为1			}			else smaller = nums[i];//更新smaller		}	}	return false;}