题目链接300. 最长递增子序列 - 力扣LeetCode

朴素做法

设元素数组为arr定义一维数组dpdp[i]表示以i位置结尾的子序列中最长的上升子序列的长度

这些子序列可以被划分成哪些子集合呢

一般集合划分用最后一个位置分类但这里最后一个位置限定了是i则可以按照倒数第二个位置进行分类

• 没有倒数第二个数
• 倒数第二个数为arr[0]
• 倒数第二个数为arr[1]
• …
• 倒数第二个数为arr[i-1]

当然不是每一个分类都存在因为有一个前提倒数第二个数比arr[i]小才能构成上升子序列

假设倒数第二个数为arr[j]最后一个数为arr[i]则以i结尾的子序列中最长上升子序列的长度就是

以j结尾的子序列中最长上升子序列长度+1

由于是从左往右推导dp数组因此在计算dp[i]时dp[j]的值一定已经计算好

我们尝试所有倒数第二个位置的分类这些分类的最大值就是以i为结尾的最长上升子序列长度

dp[i] = max(dp[j]) + 1arr[j] < arr[i]j从0到i-1

public int lengthOfLIS(int[] arr) {
    int[] dp = new int[arr.length];
    dp[0] = 1;
    int max = 1;
    for (int i = 1;i<arr.length;i++) {
        dp[i] = 1;
        for (int j = 0;j < i;j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                max = Math.max(max, dp[i]);
            }
        }
    }
    
    return max;
}

终极做法

朴素做法的时间复杂度为O(N^2)还有更好的做法时间复杂度能降到O(NlogN)

我们维护一个end数组end[i]表示

长度为i的最长上升子序列中结尾最小是多少

end数组是单调递增的

假设不是单调底层的假设i = j + 1end[i] <= end[j]

长度为i的上升子序列的最小值为end[i]那么这个子序列中第j个数一定小于end[i]而假设中end[j]大于等于end[i]和假设矛盾因此end数组一定是单调递增的

当我们遍历到第k个数时之前的数构成的上升子序列信息已经存到end数组中了

假设end中最大的长度为right

如果arr[i]比end[right]大说明可以将arr[i]压到end[right]后面构造出一个更长的上升子序列right++

否则在end数组中找第一个大于等于 arr [i]的数end[l]

因为end数组单调递增可以用二分法查找

将arr[i]替换掉原来的end[l]使其变得更小

• 因为arr[i]大于end[l-1]将arr[i]放在end[l]位置不破坏end数组的定义
• 原来的end[l]大于等于arr[l]替换后只可能使得end[l]更小维持了长度为l的上升子序列中结尾最小值的定义

代码实现如下

public int lengthOfLIS(int[] arr) {
    int[] end = new int[arr.length+1];
    int l = 0;
    int r = 0;
    int right = 1;
    end[1] = arr[0];

    for (int i = 1;i<arr.length;i++) {
        l = 1;
        r = right;

        if (arr[i] > end[r]) {
            end[++right] = arr[i];
            continue;
        }

        // 找到大于等于arr[i]的第一个数
        while (l <= r) {
            if (l == r) {
                break;
            }
            int mid = l + r >> 1;
            if (arr[i] <= end[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 将arr[i]替换掉原来的end[l]使其更小
        end[l] = arr[i];
    }

    return right;
}