LIS 최장 상승 하위 시퀀스 템플릿

1284 단어 LIS최장 상승 서브시퀀스일련 DP
O(n^2) 방법:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
 
int a[15010],dp[15010];
int n;
 
inline void ir(){
    cin>>n;
    return;
}
 
int main(){
    ir();
     
    int maxn=0;
    for(int i=1;i<=n;i++)dp[i]=1;
     
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
               dp[i]=max(dp[i],dp[j]+1);
        maxn=max(maxn,dp[i]);
    }
    cout<<maxn;
    return 0;
}

O(n log n) 방법:
#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,a[20010];
int c[20010];
int len=0;
 
int find(int x)
{
    int l=1,r=len,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(x>c[mid])l=mid+1;
        //    :     ，   x  ，      
        else r=mid-1;
    }
    return l;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 
    for(int i=1;i<=n;i++)
    {
        int k=find(a[i]);
        c[k]=a[i];
        len=max(len,k);
    }
    printf("%d",len);
    return 0;
}

주: 첫 번째는 서열 자체를 찾아낼 수 있고, 두 번째는 개수만 찾아낼 수 있다.
나만의 npm 패키지 만들기
xor의 우선순위

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage