README.md

题目

判断整形数组中是否存在三元升序子序列

这个题和最长升序子序列一样，都是整形数组中的升序子序列的问题。可以扩展为判断整形数组中是否存在n元升序子序列

解答

维护一个二元升序子序列，即使用一个变量small，和一个变量big。遍历数组：

• 如果一个数小于或等于small，则更新small
• 如果大于small，但是小于等于big，则更新big
• 如果大于big，那么就找到一个三元升序子序列

这个地方可能不太好理解的是：如果在更新完small后，出现了一个大于big的数，那么判断为找到了一个三元升序子序列。这种情况下，big的最后一次更新在small前，small，big和最后大于big的这个数的位置顺序是：big,small,大于big的数。这个顺序不是一个三元升序序列，但是我们判断结果是找到了三元升序子序列，这个解决是对的，但是上面这3个数并不是正确的升序序列

几个例子，假设初始数组如下：

2,3,1,4

处理到3时：

small = 2
big = 3

处理1。因为1小于small，所以更新small：

small = 1
big = 3

处理4。因为4大于big，所以判断为找到了三元升序子序列

此时3个数为1,3,4，但是在数组中对应的顺序是3,1,4。那为什么结果是对的？因为我们判断为true的条件是是：找到一个大于big的数。因为当找到一个大于small的数时，才会更新big，虽然这里最后更新了small，但是在最后一次更新big之前，肯定更新过small，所以数组中确实是存在升序的三元子序列。也就是说，真正的三元升序子序列是2,3,4