LeetCode 300.最长上升子序列

每天一道DP防止抑郁

每天一道BinarySearch防止自闭

很巧，这道题可以用这两种方法来解

• 动态规划
  做DP的题时，先写出状态转移方程。我开始设的dp[i]是 前i个元素的最长上升子序列，想了几十分钟，没写出状态转移方程，找不到dp[i]和dp[i - 1]的关系，把dp[i]设成前i个元素的最长上升子序列是找不到的。正确的是dp[i]为以nums[i]结尾的最长上升子序列，就是这个子序列中必须要以nums[i]结尾。

所以得到状态转移方程: dp[i] = max(dp[i], dp[j] + 1); (前提是nums[i] > nums[j])

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        int res = 1;
        Arrays.fill(dp,1); //每一个元素都可以单独作为一个上升子序列
        /*
            遍历nums数组，用当前的数 和 数组中的位置在该数之前的所有数依次比较，
            如果该数大于之前的数，那么证明可以以该数作为上升子序列的最后一个元素，
            然后用dp[j] + 1 和 dp[i] 比较，取最大的值。
         */
        for (int i = 1; i < n; 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(dp[i],res);
                }
            }
        }
        return res;
    }
}

• 二分查找 + 贪心思想
  思路：新建一个trim数组，先把nums[0]加入trim数组中，再遍历nums数组，在trim数组中找到大于num的最小数，并将其覆盖，若找不到则加到trim数组后面。** 在trim数组中找到大于num的最小数 ** 这个步骤 用二分搜索来实现。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int index = 0;
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int res = 1;
        int[] trim = new int[n];
        trim[0] = nums[0];
        for (int i = 1; i < n; i++) {
            index = bSearch(trim,0,res,nums[i]);
            trim[index] = nums[i];
            if (index == res) {
                res++;
            }
        }
        return res;
    }

    private int bSearch (int[] nums, int low, int high,int target) {
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] == target) {
                return mid;
            }else if (nums[mid] > target) {
                high = mid;
            }else {
                low = mid + 1;
            }
        }
        return low;
    }
}