1
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ What do you mean by "maximize $k$ (for all L)"? In other words, why can't you just arrange $A$ in decreasing order with $L=1$? $\endgroup$
    – Alex R.
    Jun 9, 2016 at 0:19

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think you are close but I am not sure either but it was enough for me :-) $\endgroup$ Jun 10, 2016 at 7:39
0
$\begingroup$

If you sort the array in decreasing order, then the longest increasing subsequence will be one element, and the number of them will be the length of the array, as the elements are distinct. To see how you can sort an array by swapping elements (slowly), see BubbleSort.

$\endgroup$
1
  • $\begingroup$ I know but that is obvious , I don't want the number of LIS s to be the length of the array . I want the maximum possible number of LIS s which is not always the length of the array. $\endgroup$ Jun 10, 2016 at 7:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .