How do you approach the Number of Longest Increasing Subsequence problem?

The Number of Longest Increasing Subsequence problem is best solved using state transition dynamic programming. You maintain two arrays, dp and count, to track the length of subsequences and the number of ways to form them.

What is the time complexity of the solution?

The time complexity of this solution is O(n^2) because of the nested loops comparing each element with all previous elements to update the dp and count arrays.

How can you optimize the space complexity of this problem?

The space complexity can be optimized to O(n) by using only two arrays, dp and count, instead of storing the entire state of subsequences at each step.

What other optimizations can be applied to this problem?

You can apply a Binary Indexed Tree (BIT) to reduce the complexity of updates and queries, potentially improving the performance for large input sizes.

What is the significance of the count array in the solution?

The count array tracks how many different subsequences result in the same length of LIS at a given index. This ensures that we correctly count all possible LIS that end at each index.

#673

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长递增子序列的个数

给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。注意这个数列必须是严格递增的。示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2: 输入: [2,2,2,2,2]…

数组动态规划树状数组线段树

题目描述

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意这个数列必须是严格递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示:

1 <= nums.length <= 2000
-10⁶ <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的长度，定义 $cnt[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的个数。初始时 $f[i]=1$ , $cnt[i]=1$ 。另外，定义 $mx$ 表示最长递增子序列的长度，定义 $ans$ 表示最长递增子序列的个数。

对于每一个 $nums[i]$ ，我们枚举 $nums[0:i-1]$ 中的所有元素 $nums[j]$ ，如果 $nums[j] \lt nums[i]$ ，则 $nums[i]$ 可以接在 $nums[j]$ 后面，形成一个更长的递增子序列。如果 $f[i] \lt f[j] + 1$ ，说明以 $nums[i]$ 结尾的最长递增子序列的长度增加了，那么我们需要更新 $f[i]=f[j]+1$ ，并且 $cnt[i]=cnt[j]$ 。如果 $f[i]=f[j]+1$ ，说明我们找到了一条长度与之前相同的最长递增子序列，那么我们需要将 $cnt[i]$ 增加 $cnt[j]$ 。然后，如果 $mx \lt f[i]$ ，说明最长递增子序列的长度增加了，那么我们需要更新 $mx=f[i]$ ，并且 $ans=cnt[i]$ 。如果 $mx=f[i]$ ，说明我们找到了一条长度与之前相同的最长递增子序列，那么我们需要将 $ans$ 增加 $cnt[i]$ 。

最后，我们返回 $ans$ 即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1] * n
        cnt = [1] * n
        mx = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if f[i] < f[j] + 1:
                        f[i] = f[j] + 1
                        cnt[i] = cnt[j]
                    elif f[i] == f[j] + 1:
                        cnt[i] += cnt[j]
            if mx < f[i]:
                mx = f[i]
                ans = cnt[i]
            elif mx == f[i]:
                ans += cnt[i]
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate should be comfortable explaining the state transition dynamic programming approach.
question_mark
Look for understanding of optimization techniques, such as reducing space complexity or utilizing a BIT.
question_mark
Assess the candidate's ability to handle larger inputs efficiently and discuss the trade-offs between time and space complexity.

warning

常见陷阱

外企场景

error
Forgetting to update both dp and count arrays correctly during the iterations can lead to wrong counts.
error
Misunderstanding the problem constraints can lead to inefficient solutions that fail for larger inputs.
error
Not recognizing the need for optimization, especially in terms of space complexity when handling large datasets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the number of longest increasing subsequences with additional constraints on elements.
arrow_right_alt
Consider variations that involve non-strictly increasing subsequences or variations in element restrictions.
arrow_right_alt
Handle cases with negative numbers and zeroes in the array, ensuring that these do not affect the LIS calculation.

help

常见问题

外企场景

继续练习

#1395 统计作战单位数 #493 翻转对 #406 根据身高重建队列