I wonder how to solve this question
you have array of size n where 1 <= n <= 100 and 1 <= t <= 10^7 where every element of the array is less than 10^3 the array size is n*t and for every index > n -----> array[i] = array[i-n] you only given n elements for example if n = 3 and t = 2 and the given array is {1,2,3} so you should calculate the LIS for {1,2,3,1,2,3}
what is the longest increasing subsequence? any idea !?
Since there are at most 10^3 elements in the LIS, you only need to repeat the array 10^3 times. So now the array has at most 100 * 10^3 = 10^5 elements, and you can solve for the LIS normally.
Okay thank you
What happen if LIS is not strictly increasing?
n is 100 so you need to repeat maximum 100 times
I think Hd7 is right
suppose the example n = 3 and t = 100 and for simpelecity lets say arr[i] < 3
if array = {1,1,2}
then your answer wiil be LIS of 1,1,2,1,1,2,1,1,2 which is 7 + 100-3 = 104
but the actuall answer is 100*2 = 200 as we can take 1,1 from every sequence of t
Compress $$$A$$$, and let $$$M=min(N, A)$$$. Now you have $$$O(MNlogM)$$$.
Any idea if there is duplicates ?
solution for longest nondecreasing subsequence. (let's still call it LIS)
call copy of array good if there are at least $$$2$$$ unequal elements in LIS from this copy. then there are at most $$$n$$$ good copies. and if most frequent element of array occurs $$$x$$$ times in it, then from every bad (not good) copy, there will be at most $$$x$$$ elements in LIS, and we can always position bad arrays in such a way that there are exactly $$$x$$$ elements from it in LIS, so if answer for $$$n$$$ copies is $$$A$$$, then answer for $$$t$$$ copies (if $$$t>n$$$) will be $$$A + (t-n)\cdot x$$$.