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.
↵
My idea if the following↵
↵
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.
