拼多多一面，好难。。。

文章预览

大家好，我是吴师兄。 来 看一道 砍一刀 拼多多的算法题。 手撕最长递减子序列，实际上就是稍微修改一下最长递增子序列的代码即可。 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。 定义状态 ： dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。 状态转移 ： 对于每个元素 nums[i] ，从头开始遍历到 i-1 ，如果 nums[i] 大于 nums[j] （即 nums[i] 可以接在 nums[j] 后面形成一个更长的递增子序列），则更新 dp[i] ： dp[i] = max(dp[i], dp[j] + 1) 。 初始化 ： dp 数组的每个元素初始化为1，因为每个元素本身可以构成一个长度为1的递增子序列。 结果 ： 遍历 dp 数组，找出最大的值即为最长递增子序列的长度。 代码如下： class   Solution :      def   lengthOfLIS ………………………………