提到 “最长上升子序列 ”很多人会想到自己在很早时编写的动态规划，
于是开始噼里啪啦一顿编写
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],dp[100005],maxn;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
maxn=max(maxn,dp[i]);
}
printf("%d",maxn);
return 0;
}
但是！！！！！！
怎么记录呢？
此时，大多数同学在这倒下了，聪明的同学有方法了
—————————————————————————————————————————————
我们今天讲的课是二分，说明我们可以用二分优化！
将dp变成一个维护的单调数组
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],dp[100005],cnt,ans[100005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
if(dp[cnt]<a[i])//如果可以直接加入的话就加入
{
dp[++cnt]=a[i];
ans[cnt]=a[i];//ans用来记录
continue;
}
int l=0,r=cnt;//二分进行单调性的维护 *时间复杂度更低 *
while(l+1<r)
{
int mid=(l+r)/2;
if(dp[mid]>=a[i]) //满足当前数组
r=mid;//往更小的地方走
else //不满足
l=mid;//找更大的地方
}
dp[r]=min(dp[r],a[i]);//对于结果，我们看看是否可以将dp修改
}
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);//打印答案
return 0;
}
但是！！！！
你会发现并不是字典序，又有一批同学倒下了！
—————————————————————————————————————————————
我们再次优化，可以看到，贪心会比dp更注重于局部最优解，所以可以用贪心
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],cnt,ans[100005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ans[1]=1;
cnt=1;//提前将第一个放入数组，就算有问题也可以再二分时修改
for(int i=2;i<=n;i++)
{
if(ans[cnt]<a[i])//依然是满足时直接放入
ans[++cnt]=a[i];
else
{
int l=1,r=cnt+1;//二分开始
while(l<r)
{
int mid=l+(r-l)/2;
if(a[i]<=ans[mid])//如果合法
r=mid;
else//如果不合法
l=mid+1;
}
ans[l]=a[i];//这里很重要，是直接将更小的代替原来的值
}
}
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);//打印答案
return 0;
}
但我还要再说一遍