There is such a task: A group of climbers conquered many peaks and returned to their hometown. One of the local newspapers decided to write an article about their campaign. As it turned out, during the hike, the climbers stopped for the night at a certain altitude. Since the editor-in-chief of the newspaper insists that the title of the article be “Ascending and Descending”, it was decided not to mention some days of the campaign, telling only about climbing, and if the article tells about x1, x2,…, x2k + 1- m days (x1 <x2 <... <x2k + 1), then the condition
hx1 <hx2 <... <hxk <hxk + 1> hxk + 2> ...> hx2k + 1. Find the maximum k for which you can appropriately choose 2k + 1 days. Example Input: 7 days, 1 3 2 10 7 2 1 Weekend: the number k = 2, the days themselves: 1 2 5 6 7
I would like to hear some algorithm and at least partially implementation. That's what I came up with myself, if there are clever and useful thoughts, then I ask them to note 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. But there are already two problems. First: as I understood from the condition, then there must be an odd number of elements, and then how can I drop an even number? And second: do I also need to finally output the sequence itself? and then how to restore the results? Once the problem has a dynamic programming topic, can it somehow be broken into subtasks and the results are recorded in a table? But here I do not really understand how to do it. If I have not tired you with my writing), then I ask for any help, thanks in advance
I want to add code to ++, unfortunately the task was not solved, it seems that the algorithm is still not correct
#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); for (int i = 0; i < n; ++i) { d1[i] = 1; p1[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; } } vector<int>d2(n); vector<int>p2(n); for (int i = 0; i < n; ++i) { d2[i] = 1; p2[i] = -1; for (int j = 0; j < 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 (n % 2 == 1) { if (n / 2 == i) { if (((d1[i] + d2[i]) - 1) % 2 == 1) { if (d1[i] + d2[i] - 1 > MAX) { MAX = d1[i] + d2[i] - 1; ind = i; } } continue; } } if ((d1[i] + d2[i]) % 2 == 1) { if (d1[i] + d2[i] > MAX) { MAX = d1[i] + d2[i]; ind = i; } } } fout << (MAX - 1) / 2 << endl; int pos = ind; if (pos == n / 2) pos--; vector<int>path1; while (pos != -1) { path1.push_back(pos); pos = p1[pos]; } vector<int>path2; while (ind != -1) { path2.push_back(ind); ind = p2[ind]; } 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] << " "; return 0; } 
