Practice › Dynamic Programming
Number of Longest Increasing Subsequences
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft
Print the number of strictly increasing subsequences of maximum length (subsequences are counted by index positions).
Input
First line: n. Second line: n space-separated integers.
Output
The number of longest increasing subsequences.
Constraints
- 1 ≤ n ≤ 2000
- -10^6 ≤ a[i] ≤ 10^6
- The answer fits in a 64-bit signed integer
Keep len[i] and cnt[i] for subsequences ending at i. For j < i with a[j] < a[i]: a longer length resets cnt[i] to cnt[j]; an equal length adds cnt[j].
Example 1
Input
5 1 3 5 4 7
Output
2
Example 2
Input
5 2 2 2 2 2
Output
5
Hints
- Besides the LIS length ending at i (len[i]), keep how many such subsequences there are (cnt[i]).
- For j < i with a[j] < a[i]: if len[j] + 1 > len[i], set len[i] = len[j] + 1 and cnt[i] = cnt[j]; if equal, add cnt[j] to cnt[i].
Approach
The O(n²) LIS DP extended with counts. Every increasing subsequence ending at i with maximal length comes from one ending at some earlier j with smaller value and length len[i] − 1, so the counts add up. Finally sum cnt[i] over all i whose len[i] equals the overall maximum. Counts can grow large — use 64-bit integers.
Complexity: O(n²) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n), cnt(n, 1);
vector<int> len(n, 1);
for (auto &x : a) cin >> x;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (a[j] < a[i]) {
if (len[j] + 1 > len[i]) len[i] = len[j] + 1, cnt[i] = cnt[j];
else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
}
int best = *max_element(len.begin(), len.end());
long long total = 0;
for (int i = 0; i < n; i++)
if (len[i] == best) total += cnt[i];
cout << total << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
n = len(a)
length, cnt = [1] * n, [1] * n
for i in range(n):
for j in range(i):
if a[j] < a[i]:
if length[j] + 1 > length[i]:
length[i], cnt[i] = length[j] + 1, cnt[j]
elif length[j] + 1 == length[i]:
cnt[i] += cnt[j]
best = max(length)
print(sum(c for l, c in zip(length, cnt) if l == best))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n], cnt = new long[n];
int[] len = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
len[i] = 1;
cnt[i] = 1;
}
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (a[j] < a[i]) {
if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; cnt[i] = cnt[j]; }
else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
}
best = Math.max(best, len[i]);
}
long total = 0;
for (int i = 0; i < n; i++) if (len[i] == best) total += cnt[i];
System.out.println(total);
}
}Solve Number of Longest Increasing Subsequences online · All practice problems