673-最长递增子序列的个数(Number of Longest Increasing Subsequence)

原文链接: https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence

英文原文

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Constraints:

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

中文题目

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 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。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

通过代码

高赞题解

序列 DP

与朴素的 LIS 问题（问长度）相比，本题问的是最长上升子序列的个数。

我们只需要在朴素 LIS 问题的基础上通过「记录额外信息」来进行求解即可。

在朴素的 LIS 问题中，我们定义 $f[i]$ 为考虑以 $nums[i]$ 为结尾的最长上升子序列的长度。 最终答案为所有 $f[0…(n - 1)]$ 中的最大值。

不失一般性地考虑 $f[i]$ 该如何转移：

由于每个数都能独自一个成为子序列，因此起始必然有 $f[i] = 1$；
枚举区间 $[0, i)$ 的所有数 $nums[j]$，如果满足 $nums[j] < nums[i]$，说明 $nums[i]$ 可以接在 $nums[j]$ 后面形成上升子序列，此时使用 $f[j]$ 更新 $f[i]$，即有 $f[i] = f[j] + 1$。

回到本题，由于我们需要求解的是最长上升子序列的个数，因此需要额外定义 $g[i]$ 为考虑以 $nums[i]$ 结尾的最长上升子序列的个数。

结合 $f[i]$ 的转移过程，不失一般性地考虑 $g[i]$ 该如何转移：

同理，由于每个数都能独自一个成为子序列，因此起始必然有 $g[i] = 1$；
枚举区间 $[0, i)$ 的所有数 $nums[j]$，如果满足 $nums[j] < nums[i]$，说明 $nums[i]$ 可以接在 $nums[j]$ 后面形成上升子序列，这时候对 $f[i]$ 和 $f[j] + 1$ 的大小关系进行分情况讨论：
- 满足 $f[i] < f[j] + 1$：说明 $f[i]$ 会被 $f[j] + 1$ 直接更新，此时同步直接更新 $g[i] = g[j]$ 即可；
- 满足 $f[i] = f[j] + 1$：说明找到了一个新的符合条件的前驱，此时将值继续累加到方案数当中，即有 $g[i] += g[j]$。

在转移过程，我们可以同时记录全局最长上升子序列的最大长度 $max$，最终答案为所有满足 $f[i] = max$ 的 $g[i]$ 的累加值。

代码：

[]
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }
        return ans;
    }
}

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$

LIS 问题的贪心解 + 树状数组

我们知道，对于朴素的 LIS 问题存在贪心解法，能够在 $O(n\log{n})$ 复杂度内求解 LIS 问题。

在贪心解中，我们会多开一个贪心数组 $q$，用来记录长度为 $len$ 的最长上升子序列的「最小结尾元素」为何值：**$q[len] = x$ 代表长度为 $len$ 的最长上升子序列的最小结尾元素为 $x$。**

可以证明 $q$ 存在单调性，因此每次确定 $nums[i]$ 可以接在哪个 $nums[j]$ 后面会形成最长上升子序列时，可以通过「二分」来找到满足 $nums[j] < nums[i]$ 的最大下标来实现。

对于本题，由于我们需要求最长上升子序列的个数，单纯使用一维的贪心数组记录最小结尾元素并不足以。

考虑对其进行扩展，期望能取到「最大长度」的同时，能够知道这个「最大长度」对应多少个子序列数量，同时期望该操作复杂度为 $O(\log{n})$。

我们可以使用「树状数组」维护二元组 $(len, cnt)$ 信息：

因为数据范围较大（$-10^6 <= nums[i] <= 10^6$），但数的个数为 $2000$，因此第一步先对 $nums$ 进行离散化操作；
在遍历 $nums$ 时，每次从树状数组中查询值严格小于 $nums[i]$ 离散值（利用 $nums[i]$ 离散化后的值仍为正整数，我们可以直接查询小于等于 $nums[i]$ 离散值 $-1$ 的值）的最大长度，及最大长度对应的数量；
对于流程 $2$ 中查得的 $(len, cnt)$，由于 $nums[i]$ 可以接在其后，因此首先长度加一，同时数量将 $cnt$ 累加到该离散值中。

代码：

[]
class Solution {
    int n;
    int[][] tr = new int[2010][2];
    int lowbit(int x) {
        return x & -x;
    }
    int[] query(int x) {
        int len = 0, cnt = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            if (len == tr[i][0]) {
                cnt += tr[i][1];
            } else if (len < tr[i][0]) {
                len = tr[i][0];
                cnt = tr[i][1];
            }
        }
        return new int[]{len, cnt};
    }
    void add(int x, int[] info) {
        for (int i = x; i <= n; i += lowbit(i)) {
            int len = tr[i][0], cnt = tr[i][1];
            if (len == info[0]) {
                cnt += info[1];
            } else if (len < info[0]) {
                len = info[0];
                cnt = info[1];
            }
            tr[i][0] = len; tr[i][1] = cnt;
        }
    }
    public int findNumberOfLIS(int[] nums) {
        n = nums.length;
        // 离散化
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, idx = 1; i < n; i++) {
            if (!map.containsKey(tmp[i])) map.put(tmp[i], idx++);
        }
        // 树状数组维护 (len, cnt) 信息
        for (int i = 0; i < n; i++) {
            int x = map.get(nums[i]);
            int[] info = query(x - 1);
            int len = info[0], cnt = info[1];            
            add(x, new int[]{len + 1, Math.max(cnt, 1)});
        }
        int[] ans = query(n);
        return ans[1];
    }
}

时间复杂度：$O(n\log{n})$
空间复杂度：$O(n)$

其他「序列 DP」内容

意犹未尽？可以尝试下面的「序列 DP」问题：

题目	题解	难度	推荐指数
354. 俄罗斯套娃信封问题	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
368. 最大整除子集	LeetCode 题解链接	中等	🤩🤩🤩🤩
446. 等差数列划分 II - 子序列	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
740. 删除并获得点数	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
978. 最长湍流子数组	LeetCode 题解链接	中等	🤩🤩🤩
1035. 不相交的线	LeetCode 题解链接	中等	🤩🤩🤩🤩
1143. 最长公共子序列	LeetCode 题解链接	中等	🤩🤩🤩🤩
1473. 粉刷房子 III	LeetCode 题解链接	困难	🤩🤩🤩🤩
1713. 得到子序列的最少操作次数	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
50487	115805	43.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最长递增子序列	中等
最长连续递增序列	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途