Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

tugushka's blog

Number of unique longest increasing subsequence
By tugushka, history, 10 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can you share the question link if possible ?

→ Reply