[Problem] Number of LIS

Revision en2, by nhtrnm, 2016-11-28 17:12:53

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.

Tags segment tree, lis, coci

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English nhtrnm 2016-11-28 17:12:53 1071 (published)
en1 English nhtrnm 2016-11-28 16:55:09 330 Initial revision (saved to drafts)