「最长递增子序列」系列

本周周赛第四题是一道「最长递增子序列」，本篇文章收集了三个「最长递增子序列」系列的题目，从简到繁，循序渐进！！

最长递增子序列

这道题目应该是「最长递增子序列」入门题了，之前也总结过，详情可见 动态规划设计：最长递增子序列 🔥🔥🔥

这里直接给出代码：


xxxxxxxxxx
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    // 记录最终答案，res 为 dp[] 中的最大值
    int res = 0;
    // base case
    Arrays.fill(dp, 1);
    // 自底向上依次计算 dp[i] 的值
    for (int i = 0; i < nums.length; i++) {
        // 根据区间 [0, i) 来确定 dp[i] 的值
        for (int j = 0; j < i; j++) {
            // 说明 nums[i] 可以接到以 nums[j] 结尾的子序列上
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        // 完成 dp[i] 的计算
        // 更新 res
        res = Math.max(res, dp[i]);
    }
    return res;
}

最长理想子序列

题目详情可见最长理想子序列

这道题目也是某次周赛的一道题目，之前也总结过，详情可见最长理想子序列 🔥🔥🔥

这里直接给出最优代码：


xxxxxxxxxx
public int longestIdealString(String s, int k) {
    int res = 0;
    int[] dp = new int[26];
    for (int i = 0; i < s.length(); i++) {
        // 把字母转换成对应的数字，从 0 开始
        int cur = s.charAt(i) - 'a';
        for (int j = -k; j <= k; j++) {
            int t = cur + j;
            // 在 [0, 26) 范围内
            if (t >= 0 && t < 26) dp[cur] = Math.max(dp[cur], dp[t]);
        }
        dp[cur]++;
        res = Math.max(res, dp[cur]);
    }
    return res;
}

最长递增子序列 II

题目详情可见最长递增子序列 II

这个题目和「最长理想子序列」简直不要一模一样，除了k的范围大亿点点

先不考虑超时，按照「最长理想子序列」的思路写一波


xxxxxxxxxx
public int lengthOfLIS(int[] nums, int k) {
    int ans = 0;
    // 记录以 x 结尾的子序列的长度
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int cnt = 1;
        // 向前找子序列结尾值在范围 [nums[i] - k, nums[i] - 1] 中的最大值 
        for (int j = 1; nums[i] - j >= 1 && j <= k; j++) {
            cnt = Math.max(cnt, map.getOrDefault(nums[i] - j, 0) + 1);
        }
        // 更新
        map.put(nums[i], cnt);
        ans = Math.max(ans, cnt);
    }
    return ans;
}

$O(n^2)$

[nums[i] - k, nums[i] - 1] $O(n)$ $O(logn)$

答案就是线段树，关于线段树的详解可见线段树详解 🔥🔥🔥

发现是用线段树解决，那么就是直接套模版了，建议仔细阅读「线段树详解」，相信会有不一样的收获

这里是「区间最值」且对区间进行「覆盖」的更新操作类型，下面给出代码：


class Solution {
    public int lengthOfLIS(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 查询区间 [nums[i] - k, nums[i] - 1] 的最值
            int cnt = query(root, 0, N, Math.max(0, nums[i] - k), nums[i] - 1) + 1;
            // 更新，注意这里是覆盖更新，对应的模版中覆盖更新不需要累加，已在下方代码中标注
            update(root, 0, N, nums[i], nums[i], cnt);
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
    // *************** 下面是模版 ***************
    class Node {
        Node left, right;
        int val, add;
    }
    private int N = (int) 1e5;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val = val; // 不需要累加
            node.add = val; // 不需要累加
            return ;
        }
        pushDown(node);
        int mid = (start + end) >> 1;
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if (l <= mid) ans = query(node.left, start, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
        return ans;
    }
    private void pushUp(Node node) {
        node.val = Math.max(node.left.val, node.right.val);
    }
    private void pushDown(Node node) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val = node.add;  // 不需要累加
        node.right.val = node.add; // 不需要累加
        node.left.add = node.add;  // 不需要累加
        node.right.add = node.add; // 不需要累加
        node.add = 0;
    }
}