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

Constraints - `1 ≤ n ≤ 2000` - `-1000000 ≤ value ≤ 1000000` - The answer fits in a signed 64-bit integer.