Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Besides the LIS length ending at i (len[i]), keep how many such subsequences there are (cnt[i]).
  2. 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