300. 最长递增子序列

题目来源

300. 最长递增子序列

思路

方法一

动态规划

创建一个一维的dp数组，用来记录当前位置为结尾时，最长的递增子序列的长度为多少。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        // 如果长度为0，直接返回0；
        if(len == 0){
            return 0;
        }
        int[] dp = new int[len+1];
        // 每一个数字本身就是一个长度为1的递增子序列
        dp[0] = 1;
        int ans = 1;
        for(int i = 1;i<len;i++){
            dp[i] = 1;
            // 因为是以i为结尾，所以第二遍遍历从0开始到i就可以了
            for(int j = 0;j<i;j++){
                // 如果遇到大于的就更新dp[i]
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

方法二

贪心+二分搜索

依旧是创建一个一维数组，这次的一维数组不一样，它的下标就相当于是子序列的长度；下标所对应的值代表的是：长度为下标的所有最长递增子序列中，末尾最小的数字。

举个栗子??，nums = [10,9,2,5,3,7,101,18]，

• 第一步遍历到 10 ，tail = [10]
• 第一步遍历到 9 ，tail = [9]
• 第一步遍历到 2 ，tail = [2]
• 第一步遍历到 5 ，tail = [2, 5]
• 第一步遍历到 3 ，tail = [2, 3]
• 第一步遍历到 7 ，tail = [2, 3, 7]
• 第一步遍历到 101 ，tail = [2, 3, 7, 101]
• 第一步遍历到 18 ，tail = [2,3, 7, 18]

最终得到的最大递增子序列长度为4

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] tail = new int[n + 1];
        // 初始化tail，遍历第一个数，直接放在开头
        tail[0] = nums[0];
        // len表示有序数组tail的最后一个已经赋值元素的索引
        int len = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > tail[len]) {
                len++;
                tail[len] = nums[i];
            } else {
                // 二分查找nums[i]
                // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 tail[1]
                int l = 0, r = len; 
                while (l < r) {
                    int mid = l + ((l + r) >> 1);
                    if (tail[mid] < nums[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                tail[l] = nums[i];
            }
        }
        // 索引位置从0开始
        len++;
        return len;
    }
}

参考来源

1. 官方题解
2. liweiwei1419

【题解】力扣 300. 最长递增子序列

原文：https://www.cnblogs.com/zzzzzy2k/p/14749407.html