673. 最长递增子序列的个数
题目描述
输入一个整数数组 nums，数组未排序。
子序列是从数组中删去若干元素（也可以不删）后、其余元素保持原顺序得到的序列。若子序列中后一个元素总是严格大于前一个，就称它是递增的。
在所有递增子序列中，找出长度最大的那些，返回它们的个数。由不同下标集合组成的子序列分别计数。
示例 1
输入：nums = [1,3,5,4,7] 输出：2
解释：最长长度为 4，有 [1,3,4,7] 和 [1,3,5,7] 两个。
示例 2
输入：nums = [2,2,2,2,2] 输出：5
解释：元素全相等，最长递增子序列长度为 1，共有 5 个。
数据范围
1 <= nums.length <= 2000-10^6 <= nums[i] <= 10^6
解题思路：动态规划（长度 + 个数）
在最长递增子序列 DP 的基础上多记一个计数。length[i] 表示以 nums[i] 结尾的最长长度，cnt[i] 表示达到这个长度的方案数。枚举 j < i 且 nums[j] < nums[i]：如果 length[j] + 1 更长，就更新长度并把计数重置为 cnt[j]；如果等长，就把 cnt[j] 累加到 cnt[i]。最后把 length 等于全局最大值的那些位置的 cnt 加起来。
为什么正确
处理完第 i 位后，length[i] 与 cnt[i] 对前缀 nums[0..i] 中以 i 结尾的递增子序列是精确的。
复杂度分析
时间 O(n^2)，空间 O(n)。
易错点
最后不能只取 cnt[n-1]，而是要累加所有达到最大长度的结尾位置。长度更新时要把计数重置为 cnt[j]，不能累加。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
length = [1] * n
cnt = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if length[j] + 1 > length[i]:
length[i] = length[j] + 1
cnt[i] = cnt[j]
elif length[j] + 1 == length[i]:
cnt[i] += cnt[j]
best = max(length)
return sum(c for l, c in zip(length, cnt) if l == best)class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] length = new int[n];
long[] cnt = new long[n];
java.util.Arrays.fill(length, 1);
java.util.Arrays.fill(cnt, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
cnt[i] = cnt[j];
} else if (length[j] + 1 == length[i]) {
cnt[i] += cnt[j];
}
}
}
}
int best = 0;
for (int x : length) best = Math.max(best, x);
long ans = 0;
for (int i = 0; i < n; i++) if (length[i] == best) ans += cnt[i];
return (int) ans;
}
}class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> length(n, 1);
vector<long long> cnt(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
cnt[i] = cnt[j];
} else if (length[j] + 1 == length[i]) {
cnt[i] += cnt[j];
}
}
}
}
int best = *max_element(length.begin(), length.end());
long long ans = 0;
for (int i = 0; i < n; i++) if (length[i] == best) ans += cnt[i];
return (int)ans;
}
};func findNumberOfLIS(nums []int) int {
n := len(nums)
length := make([]int, n)
cnt := make([]int, n)
for i := range length {
length[i], cnt[i] = 1, 1
}
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
if length[j]+1 > length[i] {
length[i] = length[j] + 1
cnt[i] = cnt[j]
} else if length[j]+1 == length[i] {
cnt[i] += cnt[j]
}
}
}
}
best := 0
for _, x := range length {
if x > best {
best = x
}
}
ans := 0
for i := 0; i < n; i++ {
if length[i] == best {
ans += cnt[i]
}
}
return ans
}var findNumberOfLIS = function(nums) {
const n = nums.length;
const length = new Array(n).fill(1);
const cnt = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
cnt[i] = cnt[j];
} else if (length[j] + 1 === length[i]) {
cnt[i] += cnt[j];
}
}
}
}
const best = Math.max(...length);
let ans = 0;
for (let i = 0; i < n; i++) if (length[i] === best) ans += cnt[i];
return ans;
};function findNumberOfLIS(nums: number[]): number {
const n = nums.length;
const length = new Array(n).fill(1);
const cnt = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
cnt[i] = cnt[j];
} else if (length[j] + 1 === length[i]) {
cnt[i] += cnt[j];
}
}
}
}
const best = Math.max(...length);
let ans = 0;
for (let i = 0; i < n; i++) if (length[i] === best) ans += cnt[i];
return ans;
}其他解法
动态规划对每个位置枚举所有前驱，直观但 O(n²)；贪心解法按长度分层并保持层内有序，用二分和前缀和一次求出可接的方案数。
解法 2：贪心 + 前缀和 + 二分查找 时间 O(n log n)，空间 O(n)
在求最长递增子序列长度的贪心解法上扩展。d[i] 不再只存长度为 i + 1 的最小结尾，而是按出现顺序存下所有曾经成为结尾的值，这些值单调不增。cnt[i] 是 d[i] 对应方案数的前缀和。处理 v 时，先用二分找到第一个末尾不小于 v 的 d[i]，确定 v 结尾的最长长度。再在 d[i − 1] 中二分找到第一个小于 v 的位置 k，从 k 到末尾的方案都能接上 v，用前缀和作差得到个数。最后一层前缀和的末项就是答案。
两次二分代替内层循环，降到 O(n log n)。代价是结构复杂，需要同时理解贪心求 LIS 和 d[i] 内部的单调性。
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
d, cnt = [], []
for v in nums:
lo, hi = 0, len(d)
while lo < hi:
mid = (lo + hi) // 2
if d[mid][-1] >= v:
hi = mid
else:
lo = mid + 1
i = lo
c = 1
if i > 0:
prev = d[i - 1]
lo, hi = 0, len(prev)
while lo < hi:
mid = (lo + hi) // 2
if prev[mid] < v:
hi = mid
else:
lo = mid + 1
c = cnt[i - 1][-1] - cnt[i - 1][lo]
if i == len(d):
d.append([v])
cnt.append([0, c])
else:
d[i].append(v)
cnt[i].append(cnt[i][-1] + c)
return cnt[-1][-1]class Solution {
public int findNumberOfLIS(int[] nums) {
List<List<Integer>> d = new ArrayList<>();
List<List<Long>> cnt = new ArrayList<>();
for (int v : nums) {
int lo = 0, hi = d.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
List<Integer> row = d.get(mid);
if (row.get(row.size() - 1) >= v) hi = mid;
else lo = mid + 1;
}
int i = lo;
long c = 1;
if (i > 0) {
List<Integer> prev = d.get(i - 1);
lo = 0;
hi = prev.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prev.get(mid) < v) hi = mid;
else lo = mid + 1;
}
List<Long> pc = cnt.get(i - 1);
c = pc.get(pc.size() - 1) - pc.get(lo);
}
if (i == d.size()) {
d.add(new ArrayList<>(List.of(v)));
cnt.add(new ArrayList<>(List.of(0L, c)));
} else {
d.get(i).add(v);
List<Long> cc = cnt.get(i);
cc.add(cc.get(cc.size() - 1) + c);
}
}
List<Long> last = cnt.get(cnt.size() - 1);
return (int) (long) last.get(last.size() - 1);
}
}class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
vector<vector<int>> d;
vector<vector<long long>> cnt;
for (int v : nums) {
int lo = 0, hi = d.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (d[mid].back() >= v) hi = mid;
else lo = mid + 1;
}
int i = lo;
long long c = 1;
if (i > 0) {
vector<int>& prev = d[i - 1];
lo = 0;
hi = prev.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prev[mid] < v) hi = mid;
else lo = mid + 1;
}
c = cnt[i - 1].back() - cnt[i - 1][lo];
}
if (i == (int)d.size()) {
d.push_back({v});
cnt.push_back({0, c});
} else {
d[i].push_back(v);
cnt[i].push_back(cnt[i].back() + c);
}
}
return (int)cnt.back().back();
}
};func findNumberOfLIS(nums []int) int {
d, cnt := [][]int{}, [][]int{}
for _, v := range nums {
i := sort.Search(len(d), func(m int) bool { return d[m][len(d[m])-1] >= v })
c := 1
if i > 0 {
prev := d[i-1]
k := sort.Search(len(prev), func(m int) bool { return prev[m] < v })
c = cnt[i-1][len(cnt[i-1])-1] - cnt[i-1][k]
}
if i == len(d) {
d = append(d, []int{v})
cnt = append(cnt, []int{0, c})
} else {
d[i] = append(d[i], v)
cnt[i] = append(cnt[i], cnt[i][len(cnt[i])-1]+c)
}
}
last := cnt[len(cnt)-1]
return last[len(last)-1]
}var findNumberOfLIS = function(nums) {
const d = [], cnt = [];
for (const v of nums) {
let lo = 0, hi = d.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (d[mid][d[mid].length - 1] >= v) hi = mid;
else lo = mid + 1;
}
const i = lo;
let c = 1;
if (i > 0) {
const prev = d[i - 1];
lo = 0;
hi = prev.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (prev[mid] < v) hi = mid;
else lo = mid + 1;
}
c = cnt[i - 1][cnt[i - 1].length - 1] - cnt[i - 1][lo];
}
if (i === d.length) {
d.push([v]);
cnt.push([0, c]);
} else {
d[i].push(v);
cnt[i].push(cnt[i][cnt[i].length - 1] + c);
}
}
const last = cnt[cnt.length - 1];
return last[last.length - 1];
};function findNumberOfLIS(nums: number[]): number {
const d: number[][] = [], cnt: number[][] = [];
for (const v of nums) {
let lo = 0, hi = d.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (d[mid][d[mid].length - 1] >= v) hi = mid;
else lo = mid + 1;
}
const i = lo;
let c = 1;
if (i > 0) {
const prev = d[i - 1];
lo = 0;
hi = prev.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (prev[mid] < v) hi = mid;
else lo = mid + 1;
}
c = cnt[i - 1][cnt[i - 1].length - 1] - cnt[i - 1][lo];
}
if (i === d.length) {
d.push([v]);
cnt.push([0, c]);
} else {
d[i].push(v);
cnt[i].push(cnt[i][cnt[i].length - 1] + c);
}
}
const last = cnt[cnt.length - 1];
return last[last.length - 1];
}