@@ -0,0 +1,1802 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given an unsorted array of integers, find the length of longest increasing subsequence.%0A * %3Cp%3E%0A * For example,%0A * Given %5B10, 9, 2, 5, 3, 7, 101, 18%5D,%0A * The longest increasing subsequence is %5B2, 3, 7, 101%5D, therefore the length is 4. Note that there may be more than one%0A * LIS combination, it is only necessary for you to return the length.%0A * %3Cp%3E%0A * Your algorithm should run in O(n2) complexity.%0A * %3Cp%3E%0A * Follow up: Could you improve it to O(n log n) time complexity?%0A * %3Cp%3E%0A * Tags: Dynamic Programming, Binary Search%0A * Similar Problems: (M) Increasing Triplet Subsequence, (H) Russian Doll Envelopes%0A */%0Apublic class LongestIncreasingSubsequence %7B%0A%0A    /**%0A     * DP.%0A     * Create an array to store the minimum value of a subsequence's maximum at a specific length.%0A     * How to get the value? Use binary search.%0A     * Search for the insertion point of current number.%0A     * Update the number.%0A     * If the insertion point equal to the current size, it means the array can be extended.%0A     * Then the length of Longest Increasing Subsequence can increase by 1.%0A     */%0A    public int lengthOfLIS(int%5B%5D nums) %7B%0A        int%5B%5D tails = new int%5Bnums.length%5D;%0A        int size = 0;%0A        for (int x : nums) %7B%0A            int l = 0; // Binary search for the insertion point%0A            int r = size;%0A            while (l %3C r) %7B%0A                int m = l + (r - l) / 2;%0A                if (tails%5Bm%5D %3C x) %7B%0A                    l = m + 1;%0A                %7D else %7B%0A                    r = m;%0A                %7D%0A            %7D%0A            tails%5Bl%5D = x; // Update tails, won't break its increasing trend%0A            if (l == size) %7B // x is larger than all elements%0A                size++;%0A            %7D%0A        %7D%0A        return size;%0A    %7D%0A%7D%0A

add Longest Increasing Subsequence