给定一个未排序的数组，请判断这个数组中是否存在长度为3的递增的子序列。
正式的数学表达如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
要求算法时间复杂度为O(n)，空间复杂度为O(1) 。
示例:
输入 [1, 2, 3, 4, 5],
输出 true.
输入 [5, 4, 3, 2, 1],
输出 false.
详见：https://leetcode.com/problems/increasing-triplet-subsequence/description/
C++：
方法一：超时
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,1);
for(int i=0;i<n;++i)
{
for(int j=0;j<i;++j)
{
if(nums[j]<nums[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
if(dp[i]>=3)
{
return true;
}
}
}
return false;
}
};
方法二：
使用两个指针m1和m2，初始化为整型最大值，遍历数组，如果m1大于等于当前数字，则将当前数字赋给m1；如果m1小于当前数字且m2大于等于当前数字，那么将当前数字赋给m2，一旦m2被更新了，说明一定会有一个数小于m2，那么就成功的组成了一个长度为2的递增子序列，所以一旦遍历到比m2还大的数，直接返回ture。如果遇到比m1小的数，还是要更新m1，有可能的话也要更新m2为更小的值，毕竟m2的值越小，能组成长度为3的递增序列的可能性越大。
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int m1=INT_MAX,m2=INT_MAX;
for(int a:nums)
{
if(m1>=a)
{
m1=a;
}
else if(m2>=a)
{
m2=a;
}
else
{
return true;
}
}
return false;
}
};
参考：https://www.cnblogs.com/grandyang/p/5194599.html