300. Longest Increasing Subseque

Given an unsorted array of integers, find the length of longest increasing subsequence.
基本功的题目。
先看o(N^2)的解法。

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

再看o(NlogN)的解法；

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int ans = 0;
        for (int n : nums) {
            findAndInsert(list, n);
            ans = Math.max(ans, list.size());
        }
        return ans;
    }
    private void findAndInsert(List<Integer> list, int n) {
        if (list.size() == 0) {
            list.add(n);
            return;
        }
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (list.get(m) < n) {
                l = m + 1;
            } else r = m;
        }
        if (list.get(l) >= n) {
            list.set(l, n);
        } else list.add(n);
    }
}