题解 AT2827 【LIS】

MSM2004 · 2018-12-22 14:46:50 · 题解

优化算法：用的是贪心策略 数组up[i]的意义是， up[i]中保存的是长度为i的上升子序列中结束元素最小的那个元素的值，比如长度为3的上升子序列有2个，一个最后一个元素为800，另一个最后一个元素为799，那么up[3]=799。up[i]中的元素都尽可能的小，这样才有潜力接上更多大的数。 贪心策略：我们总是希望新的元素能加入到长度最长且最后一个元素最小的序列中，这样构成的上升序列才会更有“潜力”接上更多的元素。 up[ ]数组的长度为所求

#include<iostream>
#include<algorithm>
using namespace std;
int a[100010],up[100010];
int main()
{
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    cin>>a[i];
    up[1]=a[1];
    int ans=1;
    for(int i=2;i<=m;i++)
    {
        int pos=lower_bound(up+1,up+ans+1,a[i])-(up+1)+1;//lower_bound() 返回一个迭代器，指向键值<= a[i]的第一个元素
        up[pos]=a[i];
        ans=max(ans,pos);
    }
    cout<<ans;
    return 0;
}