LeetCode : 300. Longest Increasing Subsequence 最长上升子序列

忘是亡心i 2021-06-24 16:11 679阅读 0赞

**试题**  
Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: \[10,9,2,5,3,7,101,18\]  
Output: 4  
Explanation: The longest increasing subsequence is \[2,3,7,101\], therefore the length is 4.  
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.  
Your algorithm should run in O(n2) complexity.  
Follow up: Could you improve it to O(n log n) time complexity?  
**代码**  
dp以当前位置为结尾的最长子序列。

class Solution {
        public int lengthOfLIS(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            int len = nums.length;
            int max = 0;
            int[] dp = new int[len];
            
            for(int i=0; i<len; i++){
                for(int j=0; j<i; j++){
                    if(nums[i]-nums[j]>0){
                        dp[i] = Math.max(dp[j]+1,dp[i]);
                    }
                }
                max = Math.max(max, dp[i]);
            }
            return max+1;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，679人围观）

还没有评论，来说两句吧...

相关阅读

相关 300. Longest Increasing Subsequence (Medium)——最长递增子序列

> 前言：本题目为动态规划思想的一道典型例题——最长递增子序列。 > 题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入

小灰灰/ 2023年05月29日 09:20/ 0 赞/ 60 阅读

相关 leetcode.最长上升子序列(longest-increasing-subsequence)

最长上升子序列(longest-increasing-subsequence) [题解][Link 1] 代码一 class Solution {

Myth丶恋晨/ 2022年12月27日 14:29/ 0 赞/ 65 阅读

相关 leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）

题目 [https://leetcode.com/problems/longest-increasing-subsequence/][https_leetcode.com

雨点打透心脏的1/2处/ 2022年10月12日 14:59/ 0 赞/ 198 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 70 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 174 阅读

相关 Leetcode：300. Longest Increasing Subsequence（最大增长序列）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

╰+攻爆jí腚メ/ 2022年04月05日 15:48/ 0 赞/ 178 阅读

相关 LeetCode 300.Longest Increasing Subsequence (最长上升子序列)

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释

痛定思痛。/ 2022年03月02日 16:44/ 0 赞/ 200 阅读

相关 LeetCode300最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: \[10,9,2,5,3,7,101,18\] 输出: 4 解释: 最长的上升子序列是 \[

比眉伴天荒/ 2022年01月05日 04:43/ 0 赞/ 260 阅读

相关【Leetcode】300. Longest Increasing Subsequence（最大上升子序列）

Given an unsorted array of integers, find the length of longest increasing subsequence.

叁歲伎倆/ 2021年12月16日 12:04/ 0 赞/ 238 阅读

相关 LeetCode : 300. Longest Increasing Subsequence 最长上升子序列

试题 Given an unsorted array of integers, find the length of longest increasing subseque

忘是亡心i/ 2021年06月24日 16:11/ 0 赞/ 680 阅读