최 장 상승 (하강) 서브 시퀀스 의 길이 - DP 및 그 최적화 및 nlogn 법 구하 기

최 장 엄격 한 상승 서브 시퀀스 는 매우 흔히 볼 수 있 는 문제 이다.여기 서 나 는 세 가지 방법 을 제시 하여 한 걸음 한 걸음 그것 의 속 도 를 올 렸 다.
 
DP 법
이전 방정식 f [i] = max (f [j]) + 1 (요구 a [i] > a [j])
이런 종류의 O²）이해 하기 쉽다.
 
2. DP + 트 리 배열 (또는 기타 rmq 알고리즘)
트 리 배열 은 max (f [j]) 를 최적화 하 는 데 사 용 됩 니 다. 그러나 트 리 배열 은 구간 의 최대 치 를 구 하 는 데 한계 가 있 습 니 다. 이 최대 치 는 커 질 수 밖 에 없고 줄 이면 업데이트 할 수 없습니다. 마침 f [j] 도 계속 커지 기 때문에 사용 합 니 다.
 
3. 욕심 + 2 점
배열 b 를 새로 만 듭 니 다. 배열 을 배치 하 는 데 사 용 됩 니 다. 어떤 숫자 가 끝 에 있 는 요소 보다 클 때 끝 에 꽂 으 면 최 장 상승 서브 시퀀스 의 길이 가 1 증가 한 것 을 의미 합 니 다. 이 배열 에서 작은 숫자 를 바 꿀 수 있 는 지 살 펴 보 세 요. 더 작은 숫자 를 바 꾸 면 이 수열 은 더욱 '잠재력' 을 가지 게 됩 니 다.이것 은 부분 이 원래 끝자리 보다 큰 숫자 로 가입 하 는 것 을 허용 합 니 다. 이 교체 과정 은 우리 가 서열 중의 가장 큰 숫자 를 현재 뒤쪽 의 작은 숫자 로 바 꾸 려 고 시도 한 것 으로 이해 할 수 있 습 니 다. 예 를 들 어 1, 5, 10, 6, 7, 8 에서 i = 4 시, 1, 5, 10 수열 을 1, 6, 10 으로 바 꾸 면 1, 6,... (새 숫자 연결 기대)의 수열. i = 5 에 서 는 7 이 10 으로 바 뀌 었 고 수열 은 1, 6, 7 로 바 뀌 었 다. 7 이 연 결 된 셈 이다. 그래 야 i = 6, 8 이 자 연 스 럽 게 연결 되 고 수열 은 1, 5, 6, 7, 8 로 바 뀌 어 최 장 상승 서브 시퀀스 의 길 이 를 늘 렸 다.
이렇게 해서 O (nlogn) 의 시간 복잡 도 를 만 들 었 다.
 
하위 시퀀스 의 길 이 를 최대 로 낮 추 지 않 으 려 면 find houji 를 변경 할 필요 가 없습니다. 삽입 조건 (35 줄) if (a [i] > b [len]) b [+ len] = a [i]; 의 > > > 로 바 꾸 면 됩 니 다.
 
최 장 하강 서브 시퀀스 를 요구 할 때 find houji 는 find qianqu 로 바 꾸 고 (35 줄) if (a [i] > b [len] b [+ len] = a [i], if (a [i] 다른 부분 은 최 장 상승 서브 시퀀스 의 길이 와 같 습 니 다.
 
그 중에서 find houji 와 find qianqu 는 모두 시스템 함수 로 대체 할 수 있 습 니 다.
C + + 의 라 이브 러 리 에는 2 분 검색 함수 가 두 개 있 습 니 다. C + 코드 를 사용 하면 짧 고 쓰기 편 합 니 다. lower_bound(first,last,val) ：함 수 는 비 체감 시퀀스 [first, last) (first 포함 last 포함 하지 않 음) 의 첫 번 째 값 val 보다 큰 위 치 를 되 돌려 줍 니 다. first 와 last 는 모두 포인터 형식 으로 사용 할 때 sort 와 유사 합 니 다. 아래 는 같 습 니 다. 
 
upper_bound(first,last,val) ：함수 가 비 체감 시퀀스 [first, last) 에서 첫 번 째 로 val 보다 큰 위 치 를 되 돌려 줍 니 다. 
 
코드

#include
#include
#include
using namespace std;
const int maxn=1010;


int n;
int len;
int a[maxn],b[maxn];
int find_houji(int k)//         b[ans]>=k
{
    int l=1,r=len,ans=1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(b[mid]>=k)
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return ans;
}

void get_up()
{
    len=1;b[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>b[len]) b[++len]=a[i];//    
        else
        {
            int p=find_houji(a[i]);//     a[i]   
            b[p]=a[i];//       
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i])
    get_up();
    printf("%d
",len);
    return 0;
}