### agent3889's blog

By agent3889, 6 years ago, ,

I saw this problem in codechef, can anyone tell me what is the approach to solve this problem. ?

• 0

 » 6 years ago, # | ← Rev. 2 →   0 EDIT: misunderstood the problem
•  » » 6 years ago, # ^ |   +4 This is interesting. You just solved the longest increasing subsequence problem in O(n) ? Care to explain how?
•  » » » 6 years ago, # ^ |   0 My mistake, I thought subsequence meant consecutive, thanks for correcting me.
•  » » » » 6 years ago, # ^ |   +1 No problem.On a sidenote, my solution to OP's problem has complexity O(t * n * log10000) using segment tree.
•  » » » » » 6 years ago, # ^ |   0 so what is the solution for the problem ?
•  » » » » » » 6 years ago, # ^ |   0 Ok, well I reduced the problem to the following one:You are given an array of integers and a number of queries. Each query is of the form a, b.The query means — Find out the maximum element in the range [a, b]. Also find out the number of occurences of the maximum element in that range.
•  » » » » » » » 6 years ago, # ^ |   0 sorry but it is not clear to me :( can you please describe it a little more ?
 » 6 years ago, # | ← Rev. 3 →   -10 Thank you very much , good answers ....
 » 6 years ago, # |   0 so no one ??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 this problem almost the same as find longest increasing sub-sequence.in longest increasing sub-sequence problem the dp states is dp[i] which represent the length of longest increasing sub-sequence from using only numbers from 1 to i and i'th element must be included , and it's calculated like this dp[i]= max ( dp[j] + 1) for all jdp[i] then make the value of cnt[i] equal to cnt[j]if you find j such that dp[j]+1==dp[i] then add to cnt[i] the value of cnt[j]if you find j such that dp[j]+1