Lets say , I have an array A = [A1 A2 A3 …. An] with size n.
All elements are distinct in the array. I can change positions of any two elements by swapping them .
Now , The Longest increasing sub-sequence of any such arrangement of elements of A is L.
And I have k such LIS s with length L.
For example ,
A = [23 , 98 , 67]
Here , LIS L = 2 and there are k = 2 such sequences with length = L.
[23 , 98] , [23 , 67].
How should I arrange elements of A such that I can maximize k (for all L)?
Meaning , I have an array A[] , How / In which pattern should I arrange the
elements of A so that number of longest increasing sub-sequences is maximum.
And for some N , what is the maximum possible value of k?
Lets say , I have an array [52 45 23 12 89]
How many maximum longest increasing sub-sequences (any length will do) I can make from this array by rearranging its elements ?
Best Answer
Let's say L = 2k. Then there is an array of length L that has 2^k longest increasing subsequences. The array is:
2 1 4 3 6 5 8 7 10 9 ..... 2k 2k-1
Each LIS will be of length k.
If L = 2k+1, where k>=1, then array is:
2 1 4 3 6 5 ...... 2k+1 2k 2k-1
3*(2^k-1) LIS are there, each of length k.
So, in your example, I think the answer will be 6.
EDIT: This is incomplete. At least, the answer can be improved. If we use the same strategy as above, we can ask ourselves this question,
"Choose some positive numbers whose sum is L, and the product is maximized".
For a moment, forget integers. If we solve the above problem for real numbers, then each number should be e, and there would be L/e numbers.(Can be proved using AM-GM inequality and differentiation). For integers, this would get maximized when every integer is equal to 3. If L leaves remainder 1 when divided by 3, we make the last number 4, else if it leaves remainder 2, we make the last number 2. If L is completely divisible by 3, we have no problem! Now this maximal product is the solution to the problem!
There still might be better strategies! I don't know.