The other day in COCI Round #3 I didn't solve the problem Zoltan. Turns out the problem involved counting the # of LIS (longest increasing subsequence) in an array. I never coded this before and wanted to ask Codeforces community to verify that what I do is correct.

My idea is the following:

FindNumberOfLIS(nums):
    len is an array where len[i] is the length of LIS that ends at nums[i]
    cnt is an array where cnt[i] is the number of such LIS that end at nums[i]
    for i in [1..n]:
        let maxlen be the maximum len[j] for j in [1..i-1] and nums[j] < nums[i]
        let sumcnt be the sum of cnt[j] for j in [1..i-1] and nums[j] < nums[i] and len[j] == maxlen
        then len[i] is clearly maxlen+1 and cnt[i] = sumcnt
    return cnt[j] associated with maximum len[j]

The algorithm above is O(n²). If not for the constraint nums[j] < nums[i] we could have used segment tree. Therefore what I do is sort the initial nums into sortednums and create a segment tree relative to sortednums. Now on each step I would find maxlen and sumcnt in my segment tree from 1 to position of nums[i] in sortednums. In the end I return the sumcnt on the entire segment tree.

Can anyone tell me if it's correct? And if possible, tell me how you deal with duplicates since they are pretty annoying.