No, the time complexity of the merge is O(k^2), because on each iteration it does a naive full suffix comparison (memcmp).
So the overall complexity is O(n+m+k^3).
I have to wonder why OP went through all the trouble of optimizing "create single vector max number" when the cost of computing merge is so significantly worse than that of computing single vector max number in worst case.
I am bit of confused where you get O(m+n)*min(m,n) for the merge function.
the a and b in merge function merge(a,b) sums up to k right? a+ b = k because the prep function returns out[:k]. I am guessing it should be O(k) for every position in temp and min(m,n) because the max() function?
I am so confused because there are comments above say running time is O((m+n)^3) ? I was thinking it should be O(m+n) because of prep function. and O(k) * min(m,n) *k for merge function, there is also a max() function in the return statement which runs in O(k^2) right? cause the generator have k elements in it with k length?
total would be O(m+n) + O(k) * min(m,n) *k + O(k^2) ? I am so lost.....I been thinking about this for hours. Someone please help
Try hard to understand how did you work this out!
search start is simple - start looking for next maximum number from index of previous maximum
But how much span of array should be? If i am to choose 5 items from an item of 6, and I am choosing 2nd item (selects is 4) then I should range so that there're at least 3 items left once i choose maximum, the only guaranteed way to do this is that search span ends before 3 rd item. How did you work this out? Can somebody explain???
@solocaptain It looks like DP O(mnk) solution will visit many unnecessary sub-problems. I can't give a strict proof that how many unnecessary sub-problems it visited, but we can see an example: string one is 911111111119, and string two is 911111111119, and we are looking for a four-digit max number. The answer is 9999. But if we use DP, then we consider lots of unnecessary sub-problems like (11111111119,11111111119,4), etc. So we can try greedy method. In conclusion, DP method is correct, but the method had visited lots of unnecessary sub-problems, so it's a better idea to try greedy method after you have a DP method.
I also couldn't understand the meaning of the quesion according to the examples provided at frst. After seeing some answers of the quesion, I think " the maximum number of length k " means the maximum "string" in lexicographic ordering of length k. Only in this way can the examples be right.