LC 300. 最长递增子序列

LC 300. 最长递增子序列

 

class Solution {
    
    public int lengthOfLIS(int[] nums) {
        int N = nums.length;
        if (N == 1) return 1;   // 如果数组长度位置, 那么最长递增子序列就是 1
        // dp[i] 表示, 必须以第 i 个位置结束的最长递增子序列的长度
        int[] dp = new int[N];
        dp[0] = 1;  // dp[0] 必为 1
        int ans = 1;
        for (int i = 1; i < N; i++) { 
            dp[i] = 1;
            // 扫描 0...i-1 区域的可能取值
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j])  // 找到一个可能取值
                    // 取最大的那个
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

class Solution {
    

    public int lengthOfLIS(int[] nums) {
        int N = nums.length;
        if (N == 1) return 1;
        int[] dp = new int[N];
        int size = 1;

        dp[0] = nums[0];
        for (int i = 1; i < N; i++) {
            // 找 dp 数组中第一个比 nums[i] 大
            int mostLeftBigIndex = search(dp, size, nums[i]);
            if (mostLeftBigIndex == -1) {
                // 如果找不到, 在后面追加
                dp[size++] = nums[i];
            } else {
                // 找到了, 用当前位置的值, 更新 dp 的对应位置
                dp[mostLeftBigIndex] = nums[i];
            }
        }
        return size;
    }
    // 二分查找, 找数组中第一个比 key 大
    private int search(int[] dp, int size, int key) {
        int l = 0, r = size - 1;
        int res = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (dp[m] >= key) {
                res = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return res;
    }
}