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.
Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).
Yes, the O(N2) idea is correct. You can change it a little bit, so that the segment tree idea is more intuitive and can handle dublicates. Instead of storing the length and count for each index, you should store them for a number. At each step len[i] will be the LIS ending at a number with value i. Similarly, cnt[i] will be the number of these LISes. When you are at the i-th index, just loop from 1 to nums[i] - 1 and update the length and count for nums[i]. In order to speed this up, let's use a segment tree, where the i-th leaf contains len[i] and cnt[i]. Each internal node will store the maximum length of a LIS, len, in its subtree and the number of these LISes (cnt).
Yeah so I was on the right track, thank you!
I also found out a non-segment-tree solution using two binary searches on each step. If you are interested, the link is here.