Increasing Triplet Subsequence https://leetcode.com/problems/increasing-triplet-subsequence/
Variant of longest increasing subsequence
- We need to maintain 2 variables x and y.
- x is the smallest number seen so far. x is also the smallest last number amongst all subsequences seen so far.
- If we take all increasing subsequences of size 2 and represent a subsequence as s, s; then y is min(s).
- For any new number z, if z is more than y, we have our solution.
class Solution(object): def increasingTriplet(self, nums): """ :type nums: List[int] :rtype: bool """ x,y = 2**31-1,2**31-1 for t in nums: if t < x: x=t elif x<t<y: y = t elif t > y: return True return False