首页 > 试题广场 >

最长上升子序列(一)

[编程题]最长上升子序列(一)
  • 热度指数：78107 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 且 。
数据范围：
要求：时间复杂度 O(nlogn)， 空间复杂度 O(n)
示例1

输入

[6,3,1,5,2,3,7]

输出

4

说明

该数组最长上升子序列为 [1,2,3,7] ，长度为4
算法知识视频讲解
添加回答
Java
pein531头像 pein531
经典动态规划求解 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int n = arr.length;
        if(n == 0) return 0;
        int[] dp = new int[n];     // dp[i]表示以arr[i]结尾时的最长递增子序列长度
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for(int i = 1; i < n; i++){
            for(int j = i - 1; j >= 0; j--){
                if(arr[j] < arr[i]){
                    // arr[j] < arr[i]，可以把arr[i]接在arr[j]后面，构成长度为dp[j]+1的递增子序列
                    dp[i] = Math.max(dp[i], dp[j] + 1);     // 选择能构成更长递增子序列的arr[j]
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

发表于 2021-12-11 11:44:22 回复(1)
C++
include<cc>头像 include<cc> 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        vector<int>res;
        int len = arr.size();
        for(int i=0;i<len;i++){
            if(res.size() == 0 || res.back() < arr[i]){
                res.push_back(arr[i]);
            }else{
                int j = res.size()-2;
                while(j>=0){
                    if(arr[i] > res[j])break;
                    j--;
                }
                res[j+1] = arr[i];
            }
        }
        return res.size();
    }
};

发表于 2021-11-07 18:33:16 回复(0)
Java
xkstudy头像 xkstudy 
import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int len = arr.length;
        int[] dp = new int[len + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = Integer.MIN_VALUE;
         
        for(int i = 0; i < len; i++){
            for(int j = i; j >= 0; j--){
                if(arr[i] > dp[j]){
                    dp[j + 1] = Math.min(dp[j + 1],arr[i]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= len ; i++){
            if(dp[i] >= Integer.MAX_VALUE ){
                break;
            }else{
                res = i;
            }
        }
        return res;
    }
}

发表于 2022-05-12 17:46:43 回复(2)
Java
人间水长东头像 人间水长东 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here

        // 算法核心思想：动态规划

        // 处理特殊情况
        if (arr.length == 0) {
            return 0;
        }

        // dp[i] - 表示以i位置元素为结尾的最长严格上升子序列的长度
        // i - 从0（左）往n（右）推
        int[] dp = new int[arr.length];

        // 初始化dp
        // 当只有0位置元素时，上升子序列仅有其自己，故长度为1
        dp[0] = 1;

        // 递推dp
        int result = 1;
        for (int i = 1; i < arr.length; i++) {
            int max = 1;
            // 求解dp[i]，观察dp[0 ~ i-1]的所有位置，若有小于arr[i]的，就尝试让arr[i]接在其后面，+1
            for (int j = 0; j < i; j++) {
                // 先假设以arr[j]为结尾的最长严格上升子序列只有它自己
                int length = 1;
                if (arr[j] < arr[i]) {
                    // arr[i]可以接在以arr[j]为结尾的最长上升子序列后面
                    length = dp[j] + 1;
                }
                // 更新max
                if (length > max) {
                    max = length;
                }
            }
            // 根据max记录dp[i]
            dp[i] = max;
            // 更新最终的结果，及所有位置中最大的那个值
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
}

发表于 2024-09-25 20:07:47 回复(2)
唐氏综合征头像 唐氏综合征
普通人脑溢血做法（非贪心算法） 
 public int LIS(int[] arr) {
        // write code here

        int len = arr.length;

        if (len == 0)
            return 0;
        if (len == 1)
            return 1;

        // dp 表示截止到当前的上升子数组的最大值
        int[] dp = new int[len];
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < len; i++) {
            // 每次开始的地方都要初始化为1
            dp[i] = 1;
            // 对 [j,i) 进行查找, dp[i] 记录其全局最大值
            /*
             * 因为  dp[i] = Math.max(dp[i], dp[j] + 1); 
             * 在计算的时候 j = 2 时，则可能是 dp[2] +1, 
             * 在 j=3 时，可能是 dp[3]+1, 而 dp[2] 和 dp[3] 的值在 i =2和 i=3 的时候已经计算过了，
             * 即使 arr[2] > arr[3], 我们在更新 i = 5 时的 dp[i] 的值时，也会取其较大值，
             * 因此整个遍历过程中，计算 dp[5]时，我们会在 dp[0~4] 之间找到一个最大值，
             * 并根据 arr[5] 的大小判断是否要 +1
             */
            for (int j = 0; j < i; j++) {
                // 找到一种，对于 dp[j] 来讲，多了一个元素

                if (arr[i] > arr[j]) {
                    // 此时的 dp[j] 早已在之前的循环中计算好了
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

大神做法：使用辅助数组， 
  int n = arr.length;
        int[] res = new int[n];
        int end = -1;
        for(int i = 0; i < n; i++) {
            if(i == 0 || res[end] < arr[i]) {
                res[++end] = arr[i];
            }else {

                int index = binarySearch(res, end, arr[i]);
                // 更新数组的时候，只有最长的递增子串才可能突破 res 的长度
                // 例如： {25,26,27,1,2,3,4,5}, 到 arr[i] == 3 的时候就已经更新了 res[end], arr[i] == 4 时突破长度
                // 而 {25,26,27,5,4,3,2,1 } 就不会，因为 1 开始一直往 index[0] 更新，不会影响到整体长度
                res[index] = arr[i];
            }
        }
        return end + 1;
    }

    public int binarySearch(int[] arr, int end,int target) {
        int left = 0;
        int right = end;
        while(left < right) {
            int mid = (right + left) / 2;
            if(arr[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }



发表于 2024-04-07 15:44:42 回复(0)
C++
实实实实头像 实实实实
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        //dp[i]表示到当前位置的严格上升子序列长度
        if(arr.size()<1) return 0;
        vector<int> dp(arr.size(),1);
        for(int i=1;i<arr.size();i++){
            for(int j=0;j<i;j++){
                if(arr[j]<=arr[i]){
                    if(dp[j]+1>dp[i]){
                        dp[i] = dp[j]+1;
                    }
                }
            }  
        }
        sort(dp.begin(),dp.end());
        return dp[dp.size()-1];
    }
};
发表于 2023-04-03 15:06:10 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // 时间复杂度O(N^2)，空间复杂度O(N)
        if (arr.empty()) return 0;
        int res = 1;
        vector<int> dp(arr.size(), 1);
        for (int i = 1; i < arr.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    res = max(res, dp[i]);
                }
            }
        }
        return res;
    }
};

发表于 2022-11-08 14:45:10 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def LIS(self , arr: List[int]) -> int:
        res = 0
        n = len(arr)
        dp = [1 for i in range(n)]
        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j] and dp[j]+1 > dp[i]:
                    dp[i] = dp[j]+1
                    res = max(res, dp[i])
        return res
发表于 2022-05-22 16:21:56 回复(0)
GuoGuoCaptital头像 GuoGuoCaptital
class Solution:
    def LIS(self, arr) -> int:
        # write code here
        #dp[i]表示： 包含i对应的元素的序列的最长上升子序列长度
        if not arr:
            return 0
        n = len(arr)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        res = max(dp)
        # lst = []
        # m = n - 1
        # while m:
        #     if dp[m] == res:
        #         lst.append(arr[m])
        #         res -= 1
        #     m -= 1
        return res

发表于 2025-05-29 15:58:45 回复(0)
Python3
chong_0428头像 chong_0428 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定数组的最长严格上升子序列的长度。
# @param arr int整型一维数组 给定的数组
# @return int整型
#
class Solution:
    def p(self, arr):
        if len(arr) == 0:
            return 0
        dp = [1] * (len(arr))
        dp[0] = 1
        for i in range(1, len(arr)):
            for j in range(0, i):
                if arr[i] > arr[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)
    def LIS(self , arr: List[int]) -> int:
        # write code here
        return self.p(arr)

发表于 2025-03-20 11:24:00 回复(0)
Java
clever-kalamh7o头像 clever-kalamh7o

介绍一种复杂度的做法，利用到耐心排序算法。具体代码实现与讲解可参考链接。

import java.util.*;


public class Solution {
    public int LIS (int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        int[] buckets = new int[n];
        int bucketSize = 0;

        for (int num : arr) {
            int index = BinarySearch(buckets, 0, bucketSize, num);
            if (index == bucketSize) bucketSize += 1;
            buckets[index] = num;
        }

        return bucketSize;
    }

    private int BinarySearch(int[] arr, int left, int right, int num) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
发表于 2025-02-28 15:44:53 回复(0)
Fansv587头像 Fansv587 
class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        if n == 0:
            return 0
        dp = [1] * (n)
        for i in range(n):
            for j in range(i):
                if arr[j] <= arr[i]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)
芜湖怒兽！！！
发表于 2025-02-07 13:41:47 回复(0)
C++
已成为🐬孝子头像 已成为🐬孝子

考虑到本题的本意是考察动态规划，然而给定的时间复杂度是O(n^2)，无论暴力还是未优化的动态规划都能通过，失去了题目的本意。。
但是动态规划的做法是可以优化的，使用dp数组记长度为i的上升子序列的末项为dp[i]，这使得dp数组拥有有序性，因此可以使用二分查找降低复杂度

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        // write code here
        int n = a.size(), len = 0;
        vector<int> dp(n + 1, -2147483648);
        for(int i = 0; i < n; i++)
        {
            if(a[i] == dp[len]) continue;
            if(a[i] > dp[len])
            {
                len++;
                dp[len] = a[i];
            }
            else {
                int b = lower_bound(dp.begin(), dp.begin() + len + 1, a[i]) - dp.begin();
                // b不可能等于len或len + 1
                dp[b] = min(dp[b], a[i]);
            }
        }
        return len;
    }
};
发表于 2024-11-02 09:48:11 回复(0)
双非小牛马hh头像 双非小牛马hh 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        int n=arr.size();
        if(n==1)    return 1;
        int res=0;
        // dp[i]表示以i结尾的最大上升子序列的长度
        vector<int>dp(n,1);
        
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j] ){
                    dp[i]=max(dp[j]+1,dp[i]);
                    res=max(res,dp[i]);
                }
            }
        }
        return res;
    }
};
发表于 2024-09-10 12:20:04 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        int res = 1;

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j > 0; j--) {
                if (arr[i - 1] > arr[j - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

发表于 2024-08-28 11:41:23 回复(0)
鼠鼠我卷不动了头像 鼠鼠我卷不动了 
public int LIS (int[] arr) {
        // write code here
        int[] tails=new int[arr.length];// 用于存储当前递增子序列的最小可能尾部元素
        int ans=0;
        for(int num:arr){
            int l=0,r=ans;// 在tails数组中查找插入位置，包括加到最后空的一位
            while(l<r){
                int mid=(l+r)/2;
                if(tails[mid]>=num) r=mid;// 
                else l=mid+1;
            }
            tails[l]=num;
            if(ans==l) ans++;
        }
        return ans;
    }

发表于 2024-08-08 12:17:29 回复(0)
小番茄7头像 小番茄7
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        if(arr.empty()) return 0;
        vector<int> dp(arr.size(), 1);
        for(int i = 1; i < arr.size(); i ++)
        {
            for(int j = 0; j < i ; j ++)
            {
                if(arr[i] > arr[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
发表于 2024-08-03 17:11:08 回复(0)
漂亮的王者不想上班头像 漂亮的王者不想上班
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        if(arr.length==0){
            return 0;
        }
        if(arr.length==1){
            return 1;
        }
        int[] nums=new int[arr.length];
        Arrays.fill(nums, 1);
        int maxLen = Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    nums[i]=Math.max(nums[i], nums[j] + 1);
                }
                 maxLen = Math.max(maxLen, nums[i]);
            }
        }
       
        return maxLen;
    }
}
发表于 2024-07-14 15:56:52 回复(0)
神奇的安迪面试中头像 神奇的安迪面试中 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // if(arr.length==0)return 0;
        int[] dp=new int[arr.length];
        int res=0;
        for(int i=0;i<arr.length;i++){
            if(i==0)dp[i]=1;
            else{
                int max=0;
                for(int j=0;j<i;j++){
                    if(arr[j]<arr[i]){
                        if(dp[j]>max){
                            max=dp[j];
                        }
                    }
                }
                dp[i]=max+1;
            }
            if(dp[i]>res)res=dp[i];
        }
        return res;
    }
}

发表于 2024-05-17 17:23:45 回复(0)
C++
感谢靓仔赏饭吃头像 感谢靓仔赏饭吃 
#include <memory>
#include <vector>
class Solution {
  public:
    int LIS(vector<int>& arr) {
        vector<int>d(arr.size(),1);
        int ans=0;
        if(arr.size()==1||arr.size()==0){
            return arr.size();
        }
        for(int i=1;i<arr.size();i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]&&d[i]<d[j]+1){
                    d[i]=d[j]+1;
                }
                ans=max(ans,d[i]);
            }
        }
        return ans;
    }
};

编辑于 2024-04-05 15:08:28 回复(0)
提交观点

问题信息

动态规划
难度：
73条回答 3745浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长上升子序列(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号