Longest Increasing Subsequence

1package pkg5leetcode.blind75;2 3/*4 * Longest Increasing Subsequence | LC 3005 * APPROACH: Patience sorting with binary search on tails array.6 * COMPLEXITY: Time O(n log n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC300LongestIncreasingSubsequence {11    static int lengthOfLIS(int[] nums) {12        int[] tails = new int[nums.length];13        int size = 0;14        for (int x : nums) {15            int lo = 0, hi = size;16            while (lo < hi) {17                int mid = lo + (hi - lo) / 2;18                if (tails[mid] < x) lo = mid + 1;19                else hi = mid;20            }21            tails[lo] = x;22            if (lo == size) size++;23        }24        return size;25    }26 27    public static void main(String[] args) {28        check(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}) == 4, "case1");29        check(lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}) == 4, "case2");30        System.out.println("all tests passed");31    }32 33    static void check(boolean cond, String name) {34        if (!cond) throw new AssertionError("FAILED: " + name);35        System.out.println("  PASS " + name);36    }37}