최 장 상승 서브 시퀀스 의 nlogn 알고리즘 구현 (스 택 사용)

최 장 상승 서브 시퀀스 의 nlogn 알고리즘 구현 (스 택 사용)
대체 적 인 알고리즘 사상 은 하나의 스 택 을 설정 하 는 것 입 니 다. 데이터 구조 에서 엄격 한 의미 의 스 택 은 후진 이 먼저 나 옵 니 다. 그러나 여기 스 택 중간 에 약간 다른 점 이 있 습 니 다. 중간 에 있 는 요소 도 덮어 집 니 다. 알고리즘 과정 은 첫 번 째 요소 가 스 택 에 들 어가 고 그 후에 하나의 요소 t 를 읽 지 않 았 습 니 다. 만약 에 t 가 스 택 꼭대기 요소 보다 크 면 스 택 에 들 어 갑 니 다.그것 보다 작 으 면 2 분 검색 방법 으로 스 택 에서 이러한 요 소 를 찾 습 니 다 stack [i]. stack [i] > t 와 stack [i - 1] (있 으 면) < t. 그리고 t 로 이 stack [i] 요 소 를 업데이트 합 니 다.예 를 들 어 데 이 터 를 입력 하면
5 9 4 1 3 7 6 7
그러면 스 택 의 변화 과정 은:
5
5 9
4, 9 / / 4 로 5 를 업 데 이 트 했 습 니 다.
1 9
1 3
1 3 7
1 3 6
1 3 6 7
마지막 결과, 가장 긴 증가 서브 시퀀스 의 길 이 는 스 택 의 크기 이 고 여 기 는 4 입 니 다.주의해 야 할 것 은 마지막 스 택 에 있 는 요소 가 반드시 원 하 는 순서 가 아 닙 니 다. 예 를 들 어 입력 하면
2 5 1
그럼 마지막 으로 받 은 스 택 은
1 5
실제 요구 되 는 서열 은?
2 5
이 서열 을 어떻게 구 해 야 할 지...이거...설명 을 보고 도 자신 은 아직 철저하게 연구 하지 못 했다.하하, 시간 나 면 다시 이야기 하 자.계산법 의 정확성 은 엄격 한 증명 을 거치 지 않 았 지만 생각해 보 니 맞 을 것 같 습 니 다. 하하, 게 으 름 을 피 웠 습 니 다.
코드:
/*
연습 문제 33: 최 장 증자 서열 ★ ★
질문 설명:
하위 시퀀스 란 원래 시퀀스 에서 몇 개의 요 소 를 삭제 한 후에 남 은 시퀀스 입 니 다. 문자열 'abcdefg' 를 예 로 들 어 bde 를 제거 하고 하위 시퀀스 인 'acfg' 를 얻 는 것 입 니 다.
현재 의 문 제 는 숫자 서열 을 주 는 것 이다. 가장 긴 단조 로 운 증가 서브 서열 을 요구 하 는 것 이다.
입력:
여러 조 의 테스트 데이터, 각 조 의 테스트 데이터 첫 줄 은 n (1 < = n < = 10000) 이 고, 다음 줄 은 n 개가 1e9 보다 작은 비 마이너스 정수 입 니 다.
출력:
각 그룹의 테스트 데이터 출력 줄 에 대해 각 줄 의 내용 은 가장 긴 단조 로 운 증가 서브 시퀀스 의 길이 입 니 다.
샘플 입력:
5
1 2 4 8 16
5
1 10 4 9 7
9
0 0 0 1 1 1 5 5 5
샘플 출력:
5
3
3
난이도: normal
*/

#include <cstdio>

#define MAXN 10000
long long stack[MAXN];
int n;
long long t;
int top;

int main()
{
    int i;
    int mid,high,low;
    while(scanf("%d",&n)==1 && n!=0)
    {
        scanf("%lld",&stack[0]);
        top=1;
        for(i=1;i<n;i++)
        {
            scanf("%lld",&t);
            if(t>stack[top-1])                             // 
                stack[top++]=t;
            if(t==stack[top-1])                          // 
                continue;
            else                                               // 
            {
                low=0;
                high=top-1;
                while(true)
                {
                    mid=(low+high)/2;
                    if(stack[mid]>=t && (mid==0 || stack[mid-1]<t))
                    {
                        stack[mid]=t;
                        break;
                    }
                    if(stack[mid]<t)
                        low=mid+1;
                    else
                        high=mid-1;
                }
            }
        }
        printf("%d
",top);
    }
    return 0;
}