The longest convex subsequence in an array

Question

Suppose we are given an input array of integers, how to find the longest convex subsequence satisfying the following condition:

c[i] < (c[i-1] + c[i+1]) / 2 

c[i-1] , c[i] and c[i+1] are three consecutive elements in a subsequence.

For example, if the input array is { 1, 2, -1, 0, 3, 8, 5 } , the longest convex subsequence should be: { 1, -1, 0, 3, 8 } or { 2, -1, 0, 3, 8 } .

I tried to solve this problem using the same idea of ​​dynamic programming in the "Longest Increasing Subsequence" (LIS) problem. But since each element in the subsequence depends on the previous two elements, it seems that the solution O (n ^ 2) is impossible. Thanks for the help.

Answer 1

Here is the O (N ² log N N) algorithm (and since log N is only due to sorting, we could reduce this to O (N ² log log N) or even O (N ² ) with different sorting algorithms or more complex ones priority queues):

• Create an array for each pair of elements in the input array: P[] . Elements within each pair are ordered by their index.
• Sort these pairs according to the difference in values Y2 - Y1 . In case of equal values ​​of Y2 - Y1 they should be sorted by the second index in descending order.
• Zero-initialize array L[] for subsequence lengths for subsequences ending in indices 0 .. N-1.
• For each pair from P[] (in sorted order): L[X2] = max(L[X2], L[X1] + 1) . Where X is the index of the element in the input array.
• Find the largest value in L[] . This is the length of the longest convex subsequence.
• In order to be able to recreate the subsequence, step 4 must also update the backward pointer chain. When L[X2] updated, we will create a node pointing to the node indicated by the position corresponding to X1 , then enter the point corresponding to X2 to this new node: BP_Head[X2] = new Node(BP_Head[X1]) .

The convex property c[i] < (c[i-1] + c[i+1]) / 2 can be transformed into the equivalent inequality c[i] - c[i-1] < c[i+1] - c[i] . This means that when processing pairs in sorted order, we no longer need to check the convex property. Thus, the only task in step 4 is to increase the substrings.

This simplified version of the algorithm requires O (N ² ) space. The complexity of the space can be reduced if, instead of a large array P[] we use a pre-sorted copy of the input array S[] along with a priority queue. Step # 4 takes items on top of this priority queue. To keep the size of this priority queue equal to N, we can put the element S[i+1] - S[j] into the queue only after deleting S[i] - S[j] (therefore, the queue saves only one element for each j ). The huge amount of space spent by the backward pointer forest is not required if we use the well-known DP trick to store only one backward pointer (for each index) pointing to the "middle" of the original backward pointer chain (and then repeating this algorithm recursively for the two submatrices preceding and following this "middle" backward pointer).

---

And the O (N ³ ) algorithm:

• Create a graph where each vertex corresponds to (ordered by index) a pair of array elements.
• We connect the vertices with the edge if they have one common element of the array, which is located between the remaining two elements associated with these vertices, and all three elements satisfy the convex properties. This edge should be directed to a vertex with large indices.
• Add source and target nodes and connect them to each vertex.
• Find the longest path on this chart.

This graph has O (N ² ) vertices and O (N ³ ) edges. It can be built in O (N ³ ) time; and since it is a DAG, the search for the longest path also takes O (N ³ ) time.

Answer 2

Lets name the longest convex sequence as LCS; The smallest possible length for N> 1 is 2. The algo below is self-evident.

 int LCS[N]; LCS[0] = 1; LCS[1] =2 ; for(i=2;i<N;i++) { LCS[i] = 2; for(j=1;j<i;j++) { for(k=0;k<j;k++) { if(LCS[j]-1 == LCS[k] && A[j] < (A[k] + A[i])/2 ) LCS[i] = max( LCS[i], 1+LCS[j]); } } }