1最长递增序列
简单来说就是从一串数字李找出连续的最长递增序列，暴力的思路就是通过两次循环，第一层是便利每个元素，第二层便利第一层之前的元素，如果当前元素大于前一个元素，并且以j结尾的递增子序列长度加1大于dp[i]，则更新
普通
点击查看代码
int n;
cin >> n;
int max1 = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[i] > a[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
max1 = max(max1, dp[i]);
}
cout << max1+1;
return 0;
}
点击查看代码
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int m = 1;
for (int i = 0; i < n; i++)
{
int p = lower_bound(en, en + m, a[i]) - en;
if (p >= m)
{
en[m] = a[i];
m++;
}
else
{
en[p] = a[i];
}
}
cout << m - 1;
算是个二位模板，代码理解差不多
点击查看代码
int n = envelopes.size();
int m = envelopes[0].size();
sort(envelopes.begin(), envelopes.end(), [](auto a, auto b)
{
if (a[0] == b[0]) return a[1] > b[1];
return a[0] < b[0]; });
int q=0;
for (int i = 0; i < n; i++)
{
int p = envelopes[i][1];
int o = lower_bound(f, f+q, p)-f;
if(o==q){
f[q++]=p;;
}
else{
f[o]=p;
}
}
return q;
这题不同的是是一个二维数组【x,y】且前一个y要小于后一个x，关键的是里面end数组的更新，其实end数组存的是每个数组的y，每次将新数组的x与里面存入的y进行比较，如果没有比x大的，说明当前数组的x和y都是最大的，直接存到最后面，否则，就要将比x大的第一个位置的y与当前的y进行比较，然后挑选较小的数，因为要的是最长的链，前面的数越小越利于后面的数加入
点击查看代码
int n=pairs.size();
int m=pairs[0].size();
int y=0;
sort(pairs.begin(),pairs.end());
for(int i=0;i<n;i++){
int p=pairs[i][0];
int o=pairs[i][1];
int u=lower_bound(f,f+y,p)-f;
if(u==y){
f[y++]=o;
}
else{
f[u]=min(f[u],o);
}
}
return y;