Let’s additionally define P_0 = S_{N+1} = 0.
Let’s show that it’s possible iff the following conditions hold:
-
P_1 = 1, P_{i-1} \le P_i \le P_{i-1}+1 for all i>1.
-
S_N = 1, S_{i+1} \le S_i \le S_{i+1}+1 for all i<N.
-
P_N = S_1. We will denote this value by L (which is LIS(A)).
-
P_i + S_i \ge L+1 for all 1 \le i \le N.
-
If P_i = P_{i-1} + 1 and S_i = S_{i+1} + 1 for some 1 \le i \le N, then P_i + S_i = L + 1 must hold.
Let’s first show that these conditions are necessary. The first three conditions are obvious, let’s prove the 4-th.
Proof of condition 4:
Consider any increasing subsequence of length L: A_{x_1}, A_{x_2}, \ldots, A_{x_L}. If i equals to x_K for some K, we will have P_i \ge K and S_i \ge L-K+1, so P_i+S_i \ge L+1. Now suppose not. If i<x_1, then P_i \ge 1 and S_i \ge L, if i>x_L, then P_i \ge L and S_i \ge 1, so P_i + S_i \ge L+1.
Now, suppose that x_K < i <x_{K+1} for some K. Note that as A_{x_K}<A_{x_{K+1}}, at least one of A_{x_K} < A_i, A_i < A_{x_{K+1}} must hold. If it’s the first one, then P_i \ge K+1, S_i \ge N-K, and if it’s the second, then P_i \ge K, S_i \ge N-K+1, in both cases P_i + S_i \ge L+1.
Condition 4 proved.
Proof of condition 5:
Clearly, if P_i = P_{i-1} + 1, A_i is contained in the longest increasing subsequence of A[1:i]. Similarly, if S_i = S_{i+1}+1, A_i is contained in the longest increasing subsequence of S[i:N]. So, there is an increasing subsequence of length at least P_i+S_i-1 in A, implying P_i+S_i\le L+1. As P_i+S_i \ge L+1, we get P_i+S_i = L+1.
Condition 5 proved.
Now, let’s show that these conditions are actually sufficient.
Let’s call positions i for which P_i = P_{i-1} + 1 and S_i = S_{i+1} + 1 \textbf{special}. For each of them, we will set A_i = i, and for every longest consecutive segment [C, D] without such i, we will assign values from C to D to elements P_C, P_{C+1}, \ldots, P_D in some order.
These positions from C to D can be divided into three categories:
-
Category 1: i for which P_i = P_{i-1} and S_i = S_{i+1} + 1
-
Category 2: i for which P_i = P_{i-1} + 1 and S_i = S_{i+1}
-
Category 3: i for which P_i = P_{i-1} and S_i = S_{i+1}
Suppose that there are X_1 positions of the first kind, X_2 of the second, X_3 of the third. Then, assign:
-
Values from C to C+X_1-1 to the positions of the first kind one by one;
-
Values from D-X_2+1 to D to the positions of the second kind one by one;
-
Values from D-X_2 to C+X_1 to the positions of the third kind one by one (yes, these ones will go in the decreasing order).
Let’s show that a permutation, constructed by these rules, will have correspondent arrays P and S. Let’s show that LIS(A[1:i]) = P_i, by induction by i, and the proof for S will be the same.
It’s clearly true for P_0 = 0. Now, let’s go from left to right and process segments [C, D] and special positions.
When we are processing special position i: P_i = P_{i-1}+1 indeed, as A_j<A_i for any j<i. So, if LIS(A[1:i-1]) = P_{i-1}, LIS(A[1:i]) = P_i.
Let’s now process segment [C, D] of not special positions. First, note that C is a position of type 2. Indeed, as C-1 is special, we have P_C + S_C = P_C+S_{C-1}-1 \le P_{C-1}+1 + S_{C-1}-1 = L+1, where inequality turns into equality only if P_C = P_{C-1}+1. In addition, we get P_C+S_C = L+1.
It’s also clear that P_i is equal to P_C plus the number of positions of type 2 on [C+1, i], and S_i is equal to S_C minus the number of positions of type 1 on [C+1, i]. As P_i+C_i \ge L+1 = P_C+S_C, we get that there are at least as many positions of type 2 on [C+1, i] as of type 1, for each i.
Now, let’s show that LIS(P[C:i]) equals to the number of positions of type 1 on [C:i] for any C \le i \le D, this will give what we want. Clearly, there is an increasing subsequence of size (number of positions of type 1 on [C:i]), but can’t there be a larger one? If there is one, it can’t end in a position of type 2. It also can’t contain more than 1 position of type 3 (as they go in decreasing order), and it contains strictly fewer positions of type 1 than there are positions of type 2 on the segment [C:i], as position C is also of type 2, so there is no such subsequence.
The work is done!