75 lines
1.3 KiB
C++
75 lines
1.3 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
|
|
int main()
|
|
{
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
int n;
|
|
cin >> n;
|
|
vector<int> a(n);
|
|
for (int i = 0; i < n; i++)
|
|
cin >> a[i];
|
|
|
|
vector<int> dp(n, 1);
|
|
vector<int> pre(n, -1);
|
|
int bestLen = 1;
|
|
int bestPos = 0;
|
|
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
for (int j = 0; j < i; j++)
|
|
{
|
|
if (a[j] <= a[i])
|
|
{
|
|
if (dp[j] + 1 > dp[i])
|
|
{
|
|
dp[i] = dp[j] + 1;
|
|
pre[i] = j;
|
|
}
|
|
}
|
|
}
|
|
if (dp[i] > bestLen)
|
|
{
|
|
bestLen = dp[i];
|
|
bestPos = i;
|
|
}
|
|
}
|
|
|
|
vector<int> lis;
|
|
int p = bestPos;
|
|
while (p != -1)
|
|
{
|
|
lis.push_back(a[p]);
|
|
p = pre[p];
|
|
}
|
|
reverse(lis.begin(), lis.end());
|
|
cout << bestLen << endl;
|
|
for (int x : lis)
|
|
cout << x << ' ';
|
|
|
|
cout << endl;
|
|
|
|
|
|
vector<int> dp2(n, 1);
|
|
int ans = 1;
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
for (int j = 0; j < i; j++)
|
|
{
|
|
if (a[j] > a[i])
|
|
{
|
|
dp2[i] = max(dp2[i], dp2[j] + 1);
|
|
}
|
|
}
|
|
|
|
ans = max(ans, dp2[i]);
|
|
}
|
|
|
|
cout << ans << endl;
|
|
|
|
return 0;
|
|
} |