重做300. Longest Increasing Subseq

https://leetcode-cn.com/problems/longest-increasing-subsequence/

image.png

（图片来源https://leetcode-cn.com/problems/longest-increasing-subsequence/
）

日期	是否一次通过	comment
2020-07-04	0

---

“暴力法” o(n^2)

维护一个一维 dp 数组，其中 dp[i] 表示以 nums[i] 为结尾的最长递增子串的长度，对于每一个 nums[i]，从第一个数再搜索到i，如果发现某个数小于 nums[i]，更新 dp[i]，更新方法为 dp[i] = max(dp[i], dp[j] + 1)，即比较当前 dp[i] 的值和那个小于 num[i] 的数的 dp 值加1的大小，就这样不断的更新 dp 数组，到最后 dp 数组中最大的值就是我们要返回的 LIS 的长度

   public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int res = 1;

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

                res = Math.max(res, dp[i]);
            }
        }

        return res;
    }

二分法 o(nlogn)

维护tails数组，其中每个元素是下标对应升序中最小的数值。譬如，长度为2的升序数列有[4, 5] 和 [5, 6]，那么tails[1] 存放的是5。因此，只要维护好tails数列，把tails数列的长度提交上去即可。

image.png

    public static int findPositionToReplace(int[] a, int low, int high, int x) {
        int mid;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (a[mid] == x) {
                return mid;
            } else if (a[mid] > x) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

    public static int lengthOfLIS(int[] nums) {
        if (nums == null | nums.length == 0) {
            return 0;
        }
            
        int n = nums.length, size = 0;
        int[] tails = new int[n];
        tails[size++] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > tails[size - 1]){
                tails[size++] = nums[i];
            } else {
                int position = findPositionToReplace(tails, 0, size - 1, nums[i]);
                tails[position] = nums[i];
            }
        }

        return size;
    }
}