Based on this problem, could you please tell me that, what will be the rearrangement of array [1,1,2,3,4,5,6,7,7] ?
I think the best rearrangement is [1,2,3,4,7,7,6,5,1] and here LIS(a) = 5 and LIS(a’) = 4. So, min(LIS(a), LIS(a’)) = 4.
So, based on my thought, the answer should be 4. But based on the tutorial, the answer is 5. Why?
According to the question, Your task is to determine the MAXIMUM possible beauty of the array by doing some arbitrary rearrangement.
So let’s say that I do some rearrangement and got the new array a as follows :-
a = [7, 1, 6, 4, 2, 3, 5, 1, 7]
Here you see that LIS(a) = 5 and LIS(a') = 5.
Therefore min(LIS(a), LIS(a')) = 5.
Thus our answer for this particular test case would be 5 (not 4) as were supposed to find that rearrangement which will Maximise the beauty of array a.