专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近一博士面试抖音的时候，感觉被狠狠的羞辱了，直到深夜，气的都睡不着觉。他洋洋洒洒写了一大堆，都是对抖音hr的各种吐槽。

从他的描述来看，其中有一道算法题他没做出来，这道题是：最长递增子序列，这题是LeetCode的第300题，难度是中等。估计平时做题做少了，要不然一个博士不至于这题做不出来，我们来看下。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第300题：最长递增子序列。

问题描述

来源：LeetCode第300题

难度：中等

给你一个整数数组 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 = [7,7,7,7,7,7,7] 输出：1

  • 1 <= nums.length <= 2500

  • -10^4 <= nums[i] <= 10^4

问题分析

这题让计算最长的严格递增子序列长度，有两种解决方式，一种是使用二分查找，时间复杂度是O(nlogn)，还一种是使用动态规划，时间复杂度是O(n^2)，这里我们只介绍一种动态规划的解决思路，另一种之后有时间再介绍。

定义 dp[i]表示以第 i 个数字为末尾的最长的严格递增子序列长度 ，如果要计算dp[i]，需要用num[i]和前面的数字一个个比较，如果比前面的任何一个数字大，说明加入到它的后面可以构成一个上升子序列 ，就更新dp[i]。我们就以[8，2，3，1，4]为例来画个图看一下

JAVA：

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int ans = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            // 如果当前值nums[i]大于nums[j]，说明nums[i]可以和
            // nums[j]结尾的上升序列构成一个新的上升子序列。
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                // 记录构成的最大值
                ans = Math.max(ans, dp[i]);
            }
        }
    }
    return ans;
}

C++：

public:
    int lengthOfLIS(vector

  &nums) {         vector

  dp(nums.size(), 1);         int ans = 1;         for (int i = 1; i < nums.size(); i++) {             for (int j = 0; j < i; j++) {                 // 如果当前值nums[i]大于nums[j]，说明nums[i]可以和                 // nums[j]结尾的上升序列构成一个新的上升子序列。                 if (nums[i] > nums[j]) {                     dp[i] = max(dp[i], dp[j] + 1);                     // 记录构成的最大值                     ans = max(ans, dp[i]);                 }             }         }         return ans;     }

Python：

def lengthOfLIS(self, nums: List[int]) -> int:
    dp = [1] * len(nums)
    ans = 1
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
                ans = max(ans, dp[i])
    return ans

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。