🌕 🌕 🌕 🌕 300. 最长递增子序列

难度: 🌕 🌕 🌕 🌕

• 问题描述
• 解法 1 - dp
• 输出
• 解法2 - 二分
• 输出

问题描述

---

解法 1 - dp

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 思路：
        // dp[i] = max{dp[j] + 1}, j < [0, i)
        // 以 i 为末尾下标的最长递增子序列长度
        int len = nums.length;
        int[] dp = new int[len];
        // 初始化
        Arrays.fill(dp, 1);
        int res = 1;
        // dp
        for(int i = 1; i < len; 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;
    }
}

---

输出

---

解法2 - 二分

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 思路：
        // 发牌 - 二分加速查找牌的插入位置
        int count = 0;
        int len = nums.length;
        int[] array = new int[len]; // 最多 len 个牌堆，即全部元素形成递增子序列
        array[0] = nums[0];
        count ++; // 初始有一个牌堆
        // 依次添加新牌到牌堆中
        for(int i = 1; i < len; i ++) {
            // 特殊情况特判
            if(nums[i] > array[count - 1]) {
                array[count] = nums[i];
                count ++;
                continue;
            }
            if(nums[i] <= array[0]) {
                array[0] = nums[i];
                continue;
            }
            // 二分确定插入位置
            int index = getIndex(array, 0, count - 1, nums[i]);
            array[index] = nums[i];
        }
        return count;
    }

    private int getIndex(int[] array, int left, int right, int target) {
        // 递归终止条件
        if(left >= right) {
            return left;
        }
        if(target <= array[left]) {
            return left;
        }
        int mid = left + ((right - left) >> 1);
        if(array[mid] == target) {
            return mid;
        } else if(target > array[mid]) {
            return getIndex(array, mid + 1, right, target);
        } else {
            // target < mid
            return getIndex(array, left, mid, target);
        }
    }
}

---

输出