最长递增子序列(力扣 300)Java动态规划

简介: 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

一、题目描述



给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。


子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。


示例 1:

输入:nums = [10,9,2,5,3,7,101,18]

输出:4

解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。


示例 2:

输入:nums = [0,1,0,3,2,3]

输出:4


示例 3:

输入:nums = [7,7,7,7,7,7,7]

输出:1

 

提示:

1 <= nums.length <= 2500

-104 <= nums[i] <= 104

 

进阶:

你可以设计时间复杂度为 O(n2) 的解决方案吗?

你能将算法的时间复杂度降低到 O(n log(n)) 吗?


二、思路讲解



使用动态规划。dp[i]表示以nums[i]结尾的序列中的最大升序序列。

       

首先dp数组的初值为1,因为每个数字本身都是一个升序子序列。


然后定义指针j,j∈(0, i)。当nums[j] < nums[i]时,说明nums[i]可以接在以nums[j]结尾的序列之后,此时dp[i] = max{dp[i], dp[j]+1};

     

然后找出dp数组中的最大值即可。


三、Java代码实现



class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int []dp = new int[len];
        for(int i=0; i<len; i++){
            dp[i] = 1;
        }
        for(int i=0; i<len; i++){   //遍历数组中每一个数,dp[i]表示以nums[i]结尾的最大升序子序列长度
            for(int j=0; j<i; j++){ //遍历nums[i]之前的每一个数,若nums[j]<nums[i],说明nums[i]可以接在nums[j]结尾的序列之后
                if(nums[j]<nums[i]){
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
        }
        int big = dp[0];
        for(int i=1; i<len; i++){
            if(dp[i]>big){
                big = dp[i];
            }
        }
        return big;
    }
}


四、时空复杂度


时间复杂度:        O(N^2)

     

空间复杂度:        O(N)


相关文章
|
27天前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
65 2
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
48 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
50 1
|
4月前
|
Arthas 监控 算法
JVM成神路终章:深入死磕Java虚拟机序列总纲
JVM成神路终章:深入死磕Java虚拟机序列总纲
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
76 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
53 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
34 0
|
3月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
35 0