The sequence increases and decreases in turn

Question

Suppose we have a sequence of integers of a given length n . We want to remove some elements (maybe not) so that the sequence increases and decreases in turn as a result. This means that each element must have neighboring elements, both large and smaller than themselves. For example, 1 3 2 7 6 and 5 1 4 2 10 both sequences increase and decrease in turn. We want to remove some elements in order to transform our sequence in this way, but we also want to maximize the sum of the remaining elements. So, for example, from the sequence 2 18 6 7 8 2 10 we want to remove 6 and make it 2 18 7 8 2 10 .

I am looking for an effective solution to this problem. The example above shows that the most naive greedy algorithm (deleting every first element that breaks the sequence) will not work - it will delete 7 instead of 6 , which will not allow to maximize the sum of the remaining elements. Any ideas how to solve ( O(n) or O(n log n) possible) efficiently and correctly?

Answer 1

For each element of the sequence with index i we calculate F(i, high) and F(i, low) , where F(i, high) will be equal to the largest sum of the subsequence with the required characteristics, which ends with the i th element and this element is a "high peak". (I will explain mainly the "high" part, the "low" part can be done in a similar way). We can calculate these functions using the following relationships:

The answer is maximum among all the values ​​of F(i, high) and F(i, low) .

This gives us a fairly simple solution for dynamic programming with time complexity of O(n^2) . But we can go further.

We can optimize the calculation of the part max(F(j,low)) . We need to find the largest value among the previously calculated F(j, low) with the condition a[j] < a[i] . This can be done using tree segments .

First of all, we “squeeze” our initial sequence. We need the real value of the element a[i] only when calculating the sum. But we need only the relative order of the elements when checking that a[j] less than a[i] . Thus, we will compare each element with its index in an array of sorted elements without duplicates. For example, the sequence a = 2 18 6 7 8 2 10 will be translated to b = 0 5 1 2 3 0 4 . This can be done in O(n*log(n)) .

The largest element b will be less than n , as a result we can build a tree of segments on the segment [0, n] with each node containing the largest amount in the segment (we need two segment trees for the "high" and "low" parts, respectively). Now describe step i algorithm:

• Find the largest sum max_low on the segment [0, b[i]-1] using the tree of "low" segments (initially all nodes of the tree contain zero).
• F(i, high) is equal to max_low + a[i] .
• Find the largest sum max_high on the segment [b[i]+1, n] using the tree of high-altitude segments.
• F(i, low) is equal to max_high + a[i] .
• Update the segment [b[i], b[i]] tree of "high" segments with the value F(i, high) , recalculating the maximum values ​​of the parent nodes (and [b[i], b[i]] node).
• Do the same for the tree with the smallest segment and F(i, low) .

Complexity analysis: b computing the sequence O(n*log(n)) . The max / update operations in a tree segment have complexity O(log(n)) , and of these, O(n) . The overall complexity of this algorithm is O(n*log(n)) .