Please explain Wavio Sequencing more clearly for me please there's a picture of the decription and also comment on the code below to know what each line is doing. It is in C++ #include #include #include using namespace std; // LIS[i] stores the maximum length of S's LIS ending at i. void doLIS(const vector &S, vector &LIS) { vector L(S.size()); size_t lisCount = 0; for (size_t i = 0; i < S.size(); ++i) { size_t pos = lower_bound(L.begin(), L.begin() + lisCount, S[i]) - L.begin(); L[pos] = S[i]; if (pos == lisCount) ++lisCount; LIS[i] = pos + 1; } } int main() { size_t N; while (cin >> N) { vector S(N); for (int i = 0; i < N; ++i) cin >> S[i]; vector LIS(N), LDS(N); doLIS(S, LIS); reverse(S.begin(), S.end()); doLIS(S, LDS); reverse(LDS.begin(), LDS.end()); size_t maxLIS = 0; for (size_t i = 0; i < LIS.size(); ++i) { /** Suppose S[] = 1 3 6 5 LIS[] = 1 2 3 3 LDS[] = 1 1 2 1 then we can pick 1 6 5 or 3 6 5. */ maxLIS = max(maxLIS, 2 * min(LIS[i], LDS[i]) - 1); } cout << maxLIS << endl; } return 0;
Please explain Wavio Sequencing more clearly for me please there's a picture of the decription and also comment on the code below to know what each line is doing. It is in C++
#include <iostream>
#include <
#include <algorithm>
using namespace std;
// LIS[i] stores the maximum length of S's LIS ending at i.
void doLIS(const vector<size_t> &S, vector<size_t> &LIS)
{
vector<size_t> L(S.size());
size_t lisCount = 0;
for (size_t i = 0; i < S.size(); ++i)
{
size_t pos = lower_bound(L.begin(), L.begin() + lisCount, S[i])
- L.begin();
L[pos] = S[i];
if (pos == lisCount)
++lisCount;
LIS[i] = pos + 1;
}
}
int main()
{
size_t N;
while (cin >> N)
{
vector<size_t> S(N);
for (int i = 0; i < N; ++i)
cin >> S[i];
vector<size_t> LIS(N), LDS(N);
doLIS(S, LIS);
reverse(S.begin(), S.end());
doLIS(S, LDS);
reverse(LDS.begin(), LDS.end());
size_t maxLIS = 0;
for (size_t i = 0; i < LIS.size(); ++i)
{
/** Suppose S[] = 1 3 6 5
LIS[] = 1 2 3 3
LDS[] = 1 1 2 1
then we can pick 1 6 5 or 3 6 5.
*/
maxLIS = max(maxLIS, 2 * min(LIS[i], LDS[i]) - 1);
}
cout << maxLIS << endl;
}
return 0;
}
Step by step
Solved in 2 steps
