【Leetcode 热题 100】300. 最长递增子序列

问题背景

给你一个整数数组 $nums$，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，$[3,6,2,7]$ 是数组 $[0,3,1,6,2,2,7]$ 的子序列。

数据约束

• $1\le nums.length\le 2500$
• $-10^4\le nums[i]\le 10^4$

解题过程

子序列而不是子数组，优先考虑回溯法而不是滑窗。
递归方法中必须要有一个下标表示当前要选择的数字的位置，选或不选的方法还需要额外记录子序列中前一个数相关的信息，否则不能保证严格递增。因此，这题选择选哪一个的做法代码更简洁。

对于动态规划问题，有一种优化时间复杂度的方案是交换状态和状态值，这题可以在数组中维护子序列末尾元素的最小值，遍历数组的过程中只有两种操作：添加或修改元素。
修改的一定是不小于当前元素的第一个元素，如果没有这样的元素，就应将新元素添加到末尾。
配合二分查找，这样可以将时间效率优化到 $O(NlogN)$ 这个量级。

具体实现

递归

class Solution {
    private int[] nums;
    private int[] memo;

    public int lengthOfLIS(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dfs(i));
        }
        return res;
    }

    private int dfs(int i) {
        if(memo[i] > 0) {
            return memo[i];
        }
        for (int j = 0; j < i; j++) {
            if(nums[j] < nums[i]) {
                memo[i] = Math.max(memo[i], dfs(j));
            }
        }
        return ++memo[i];
    }
}

递推

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int res = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            res = Math.max(res, ++dp[i]);
        }
        return res;
    }
}

贪心

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int res = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            res = Math.max(res, ++dp[i]);
        }
        return res;
    }
}