Find number of unique longest increasing subsequence in array a.
Constraints : 1 <= Lenght of a <= 5000, 0 < a[i] < 2^31
Example input :
4
1 2 2 3
Example output :
1
Help me :v.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Find number of unique longest increasing subsequence in array a.
Constraints : 1 <= Lenght of a <= 5000, 0 < a[i] < 2^31
Example input :
4
1 2 2 3
Example output :
1
Help me :v.
Name |
---|
Calculate :
dp[i] = longest increasing subsequence that ends at position i.
dp[i] = max(dp[j] + 1) with a[j] < a[i], j < i
cnt[i] = number of unique longest increasing subsequences that end at position i.
If there was no restriction for the subsequences to be unique,
cnt[i] would be equal to sum of (cnt[j] with j < i, a[j] < a[i], dp[j] is maximum).
Notice that when calculating cnt[i], if we have 2 positions k < j < i, with A[j] = A[k] and A[j] < A[i], and both dp[j] and dp[k] are maximum, we only need to add cnt[j] to cnt[i]. (i.e every unique longest subsequence that ends at k, can also end at j.)
So cnt[i] = sum(cnt[j] | j < i, a[j] < a[i], dp[j] is maximum and j = last appearance of A[j] in [1, j]).
Number of total unique longest increasing subsequences will be :
sum of (cnt[pos] such that dp[pos] in maximum, pos = last appearance of A[pos] in [1, N] where N = number of elements).
can you share the question link if possible ?