How Many Are Longest
Count the strictly increasing subsequences of MAXIMUM length. Two are different if they use different positions, even where the values coincide.
1 3 5 4 7 -> 2 the longest are length 4: 1 3 5 7 and 1 3 4 7
2 2 2 2 2 -> 5 the longest are length 1, and there are five of them
Problem #452 finds the length. Counting how many achieve it needs a second array beside it, and the interaction between the two is where this goes wrong.
len[i] the length of the longest increasing subsequence ending at i
cnt[i] how many of that length end at i
For each j < i with a[j] < a[i]:
len[j] + 1 > len[i] -> len[i] = len[j] + 1; cnt[i] = cnt[j] REPLACE
len[j] + 1 == len[i] -> cnt[i] += cnt[j] ADD
The distinction is the whole problem. Finding a longer subsequence discards every
count accumulated so far, because those counts belong to a shorter length. Finding
an equally long one adds to it. Using += in both cases, or = in both, is the
classic error and gives a number that looks plausible.
The answer sums cnt[i] over every i where len[i] equals the maximum, not just
the last such i, since several positions can end a longest subsequence.
2 2 2 2 2 is worth checking by hand: nothing is strictly increasing, so every
single element is a longest subsequence and the answer is 5, not 1.