最长上升子序列
$$ O(N^2) $$
$$
f[i]—集合:所有以i为结尾的上升子序列;性质:集合里上升子序列长度的最大值。
$$
#include <iostream>
using namespace std;
const int n = 1100;
int f[n], a[n];
int N;
int main()
{
cin >> N;
for (int i = 1; i <= N; i++)
cin >> a[i];
for (int i = 1; i <= N; i++)
{
f[i] = 1; // 只有第i个
for (int j = 1; j <= i - 1; j++) // 寻找子序列的倒数第二个数j
if (a[i] > a[j]) // 肯定要满足条件呀 注:看是否要求严格递增
f[i] = max(f[i], f[j] + 1);
}
// 下面的循环可以省去,res在上面求
int res = 0;
for (int i = 1; i <= N; i++)
res = max(res, f[i]);
cout << res;
return 0;
}
记录路径:
for (int i = 1; i <= N; i++)
{
f[i] = 1;
for (int j = 1; j <= i - 1; j++)
if (a[i] > a[j] && f[i] < f[j] + 1)
{
f[i] = f[j] + 1; // 存下来状态转移就行
path[i] = j; // 记录路径
}
}
int res = 0, index = 1;
for (int i = 1; i <= N; i++)
{
if (res < f[i])
res = f[i], index = i;
}
cout << res << endl;
while (index != 0)
{
cout << a[index] << ' ';
index = path[index];
}
#include <iostream>
#include <algorithm>
using namespace std;
const int n = 110;
int N;
int fa[n], fb[n];
int a[n];
int main()
{
cin >> N;
for (int i = 1; i <= N; i++)
cin >> a[i];
for (int i = 1; i <= N; i++)
{
fa[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] > a[j])
fa[i] = max(fa[i], fa[j] + 1);
}
for (int i = N; i >= 1; i--)
{
fb[i] = 1;
for (int j = N; j > i; j--)
{
if (a[i] > a[j])
fb[i] = max(fb[i], fb[j] + 1);
}
}
int res = 0;
for (int i = 1; i <= N; i++)
{
res = max(fa[i] + fb[i] - 1, res);
}
cout << N - res;
return 0;
}