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