@@ -0,0 +1,1777 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A/**%0A * Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.%0A * %3Cp%3E%0A * Formally the function should:%0A * Return true if there exists i, j, k%0A * such that arr%5Bi%5D %3C arr%5Bj%5D %3C arr%5Bk%5D given 0 %E2%89%A4 i %3C j %3C k %E2%89%A4 n-1 else return false.%0A * Your algorithm should run in O(n) time complexity and O(1) space complexity.%0A * %3Cp%3E%0A * Examples:%0A * Given %5B1, 2, 3, 4, 5%5D,%0A * return true.%0A * %3Cp%3E%0A * Given %5B5, 4, 3, 2, 1%5D,%0A * return false.%0A * %3Cp%3E%0A * Similar Problems: (M) Longest Increasing Subsequence%0A */%0Apublic class IncreasingTripletSubsequence %7B%0A%0A    private IncreasingTripletSubsequence i;%0A%0A    /**%0A     * DP.%0A     * Find three numbers.%0A     * Find two numbers first, then find one that's larger than both.%0A     * n1 means the minimum of subsequences of length 1.%0A     * n2 means the minimum of subsequences of length 2.%0A     */%0A    public boolean increasingTriplet(int%5B%5D nums) %7B%0A        int n1 = Integer.MAX_VALUE;%0A        int n2 = Integer.MAX_VALUE;%0A        for (int n : nums) %7B%0A            if (n %3C= n1) %7B%0A                n1 = n;%0A            %7D else if (n %3C= n2) %7B%0A                n2 = n;%0A            %7D else %7B%0A                return true;%0A            %7D%0A        %7D%0A        return false;%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        i = new IncreasingTripletSubsequence();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        int%5B%5D input = %7B1, 2, 3, 4, 5%7D;%0A        Assert.assertTrue(i.increasingTriplet(input));%0A        input = new int%5B%5D%7B5, 4, 3, 2, 1%7D;%0A        Assert.assertFalse(i.increasingTriplet(input));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        i = null;%0A    %7D%0A%0A%7D%0A

add Increasing Triplet Subsequence