300. 最长递增子序列 (动态规划)

300. 最长递增子序列 (动态规划)

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 1) return nums.length;
        // 创建dp数组
        int[] dp = new int[nums.length];
        // 将dp数组每个位置都先用1填充
        Arrays.fill(dp,1);
        // 定义结果长度
        int res = 0;
        // 遍历dp数组
        for(int i = 0;i < dp.length;i++){
            // 遍历子序列
            for(int j = 0;j < i;j++){
                // 若之前的子序列小于原数组当前元素
                if(nums[j] < nums[i]){
                    // 计算自身以及子序列的最大递增自学列个数
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                // 取前一个结果和最新的递增子序列的最大值
                res = Math.max(dp[i],res);
            }
        }
        return res;
    }
}

https://www.bilibili.com/video/BV19b4y1R7K3?from=search&seid=3889564539053194036&spm_id_from=333.337.0.0

上一篇:基于深度学习的复杂背景下目标检测研究—论文解读


下一篇:300.最长递增子序列