算法1
(最长上升子序列没优化版本) $O(n^3)$
时间复杂度
有三层循环,而且最坏的情况有可能完全遍历到三层循环,所以是最坏的情况是 n 的三次方.
看视频(基础课,提高课)
C++ 代码 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N];
int n;
int f[N][N];
int main(void)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j])
{
f[i][j] = max(f[i][j], 1); // b 数组是空的情况 (b 数组只有一个元素, 所以前一个元素没有是 0)
for(int k = 1; k <= j; k++) // 这里类似于(求最长上升子序列了) (在 b[j] 的前面找,所以 k < j)
{
if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1); // 加 1 是表示 a[i] == b[j] 的情况
}
}
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
C++ 代码 2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
int n;
int main(void)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][j]; // 这种情况不管 a[i] 和 b[j] 是不是相等都要做一下的
视频右半部分不包含 a[i] 的情况 (肯定存在)
包含了 a[i], 并且 a[i],b[j] 都是最后一个所以相等
if(a[i] == b[j]) // 视频左半部分包含 a[i] 的情况 (不一定存在)
{
f[i][j] = max(f[i][j], 1); // 左半部分为空的情况
for(int k = 1; k < j; k++) // 对 b 数组进行最大长度的遍历 (b 数组控制最大长度, a 数组控制公共的问题)
{
if(b[j] > b[k])
{
f[i][j] = max(f[i][j], f[i][k] + 1);
}
}
}
}
int res = 0; // 因为 b 数组控制的是最长度问题,所以遍历 b 数组求最大 (长度)
for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}
算法2
(最长上升子序列的优化版本) $O(n^2)$
具体优化(等价变形的优化)过程,对比没优化的代码进行理解更好理解,注意等价变形的理解.
时间复杂度
用一个变量 maxx 优化了一层 for 循环,所以是 二次方.
看视频(基础课,提高课)
C++ 代码
// 优化后的代码能 Ac (没优化的不能,最差的情况时 n^3,并且有一个数据专门卡这个情况的)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N];
int n;
int main(void)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int j = 1; j <= n; j++) cin >> b[j];
for(int i = 1; i <= n; i++)
{
int maxx = 1;
for(int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = max(f[i][j], maxx); // f[i][j] = maxx;
// 对比没优化的代码来好理解 (等价变形)
// 因为下面没优化的情况 (a[i] == b[j], 不用管 i j 的大小,a[i] 的数值是 == b[j] 的替换的作用,所以可以用 a[i] 替换 b[j] 优化了)
// j 还是从 1 开始找的, j == i (j < i) 的时候就自动停下了
if(b[j] < a[i]) maxx = max(f[i][j] + 1, maxx); // (这里的 j 类似于没优化时的 k)
}
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}