[AlgorithProblem] Number of LIS
Difference between en1 and en2, changed 1,071 character(s)
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 thean array. I never wrotecoded this before and wanted to ask Codeforces community to verify that what I want to do is correct.↵

My idea if the following↵
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^2)$. 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.

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)