It is necessary from a given numerical sequence A of length n to cross out the minimum number of elements so that the remaining elements form a strictly increasing almost everywhere subsequence, i.e. containing no more than one discontinuity - pairs (ai, ai + 1) of successive elements, the second of which more than the first. The constructed algorithm must have O (n log n) labor input. In the output file to display the length of the greatest sequence. Here is my code, but I don’t take into account quite a few options here, as it turned out. Tell me, please, the solution algorithm

#include<iostream> #include<fstream> #include<algorithm> #include<vector> #include<iomanip> using namespace std; int const INF=2000000000; int main() { ifstream fin("input.txt"); ofstream fout("output.txt"); int n; fin>>n; vector<int>A; int i; int N=0; while(fin>>i) { A.push_back(i); N++; } vector<int>d(N); d[0] = -INF; for(int i=1;i<N;i++) { d[i]=INF; } int len; for (int i=0; i<n; i++) { int j = int (upper_bound (d.begin(), d.end(), A[i]) - d.begin()); if (d[j-1] < A[i] && A[i] < d[j]) { d[j] = A[i]; len=j; } } if(len==n) { fout<<len; } else fout<<len+1; return 0; }

    1 answer 1

    We divide the solution of the problem into two stages.

    1. Finding the longest increasing subsequence.

    Based on: e-maxx .

    Let n be the length of the sequence a_0, ..., a_n.

    The problem is solved by dynamic programming, the array is filled int d [n + 1], d [k] = the length of the largest increasing subsequence, ending strictly in a_k; .

    Dynamic formula:

    Formula dynamics

    The asymptotics of such an algorithm is obtained equal to O (n ^ 2), one n is the run in d, the second n is the run from 0 to k to calculate the next value of d [k] (in the formula).

    This algorithm can be optimized to O (nlogn) using a binary search. Since d [k - 1] <d [k], and each element of the sequence a_i updates no more than one cell d, when applying the formula above, a binary search is sufficient to find the first number that is strictly greater than a_i and update the corresponding element using the formula above .

    Implementation:

     std::vector<int> d(MAXN); d[0] = -INF; for (int i=1; i<=n; ++i) d[i] = INF; for (int i=0; i<n; i++) { int j = int (std::upper_bound (d.begin(), d.end(), a[i]) - d.begin()); if (d[j-1] < a[i] && a[i] < d[j]) d[j] = a[i]; }

    Asymptotics of the latest implementation of O (nlogn) that suits us.

    The answer is the value of the last element of the array d;

    2. Search for the two largest subsequences.

    Similarly to item (1), we can find the largest decreasing subsequence, only we will look for it for the inverted sequence b_i = a_ {n - i}. Fill in this way two arrays d1 [n + 1] and d2 [n + 2]. Then we will have in d1 [k] the length of the largest increasing subsequence ending in position k, and in d2 [k] the length of the greatest increasing subsequence beginning in position k. We can build two such arrays in O (nlogn), then with one run we find the maximum of the sum d1 [k] + d2 [k], which corresponds to k and this is the break point, the sum is the length of the largest subsequence with one break.

    Final complexity: O (nlogn) + O (nlogn) + O (n) = O (nlogn), as required.

    • Thanks, I will try to implement now. How do you know this algorithm can advise the literature? Because I implemented the first part in the task, but there is no second part - Artem
    • one
      The first point is with emaks, there is a link above (from there the answer is, and actually written off). The second one - I myself invented it, it is easy to invent it :) And according to literature - Kormen, Algorithms: Construction and analysis, probably, this is one of the best books on algorithms in general. - zcorvid
    • Only here is one discrepancy. In paragraph 1, you say that d stores the length of the largest increasing subsequence terminating strictly in k, but according to the code given, it turns out that in d we store the element from the sequence, not the length - Artem
    • The problem is solved, only you slightly misinterpreted its implementation and the actual code. But the idea itself is great, thank you so much. If someone is interested in this task, then write, I will help with joy - Artem
    • Happy to help. I think it would be nice if you write a corrected piece of code for clause 1 (I really have a cant there, I copied it from the email without looking at what was in it). For those who will read this question and answer in the future, your addition will be very useful. - zcorvid