The input is given a sequence of numbers. it is necessary to find the length of the subsequence and the subsequence itself such that it will have the greatest odd length and for it the condition hx1 <hx2 <... <hxk <hxk + 1> hxk + 2> ...> hx2k + 1 is satisfied (explanation hx1, hx2, hx3 ... these are elements of a sequence). I have already asked this question, but it did not work out. This is what I came up with: This is what I came up with myself, if there are clever and useful thoughts, then please note them and say that I am on the right track :) So, first of all I would find the greatest increasing subsequence. I seem to be able to implement such an algorithm. In the next step, I want to find the greatest diminishing subsequence. At the same time, during all of these findings, I would write the size of a subsequence that strictly ends in a given place according to the index of each element of the sequence. And in the end, it turns out that I can loop through the arrays in which I wrote information about the length of the increasing subsequence ending in this element and about decreasing ending in this element. And the largest amount of a given index in two arrays is the answer to my problem. Here is my code, which crashes on most of the tests, it is not clear why. Please help me find a bug? I don't understand what I'm doing wrong. And it also happened that one of my tests took off in time. Time 1s, and 1 <= n <= 100000.
#include<iostream> #include<fstream> #include<algorithm> #include<vector> #include<iomanip> using namespace std; int main() { ifstream fin("input.txt");//report.in ofstream fout("output.txt");//report.out int n; fin >> n; vector<int>A; vector<int>B(n); int i; int j = n - 1; while (fin >> i) { A.push_back(i); B[j] = i; j--; } vector<int>d1(n); vector<int>p1(n); vector<int>d2(n); vector<int>p2(n); for (int i = 0; i < n; ++i) { d1[i] = 1; p1[i] = -1; d2[i] = 1; p2[i] = -1; for (int j = 0; j < i; ++j) { if (A[j] < A[i]) if (1 + d1[j] > d1[i]) { d1[i] = 1 + d1[j]; p1[i] = j; } if (B[j] < B[i]) if (1 + d2[j] > d2[i]) { d2[i] = 1 + d2[j]; p2[i] = j; } } } int MAX = 0; int ind; bool p = true; for (int i = 0; i < n; i++) { if (d1[i] + d2[i] > MAX) { if (i != n - 1) { MAX = d1[i] + d2[i]; ind = i; } } } if (d1[ind] >= d2[ind]) { int pos = ind; int pos2 = n - ind - 2; vector<int>path1; while (pos != -1) { path1.push_back(pos); pos = p1[pos]; } vector<int>path2; while (pos2 != -1) { path2.push_back(pos2); pos2 = p2[pos2]; } if ((path1.size() + path2.size()) % 2 == 1) { fout << (path1.size() + path2.size() - 1) / 2 << endl; for (int i = path1.size() - 1; i >= 0; i--) fout << path1[i] + 1 << " "; for (int i = 0; i < path2.size(); i++) fout << n - path2[i] << " "; } else { fout << (path1.size() + path2.size() - 2) / 2 << endl; for (int i = path1.size() - 2; i >= 0; i--) fout << path1[i] + 1 << " "; for (int i = 0; i < path2.size(); i++) fout << n - path2[i] << " "; } } else { int pos = n - ind - 2; int pos2 = ind; vector<int>path1; while (pos != -1) { path1.push_back(pos); pos = p1[pos]; } vector<int>path2; while (pos2 != -1) { path2.push_back(pos2); pos2 = p2[pos2]; } if ((path1.size() + path2.size()) % 2 == 1) { fout << (path1.size() + path2.size() - 1) / 2 << endl; for (int i = path1.size() - 1; i >= 0; i--) fout << path1[i] + 1 << " "; for (int i = 0; i < path2.size(); i++) fout << n - path2[i] << " "; } else { fout << (path1.size() + path2.size() - 2) / 2 << endl; for (int i = path1.size() - 1; i >= 0; i--) fout << path1[i] + 1 << " "; for (int i = 0; i < path2.size() - 1; i++) fout << n - path2[i] << " "; } } return 0; } 