최 장 단조 증가 서브 시퀀스

최 장 단조 로 운 서열 의 동적 계획 최적화 문제
 
{9, 4, 3, 2, 5, 4, 3, 3, 3, 2, 3, 2} 의 최 장 체감 서열 은 {9, 5, 4, 3, 2} 이다.
    흔히 볼 수 있 는 해법 은 배열 서열 을 옮 겨 다 니 며 하나의 배열 요 소 를 옮 겨 다 닐 때마다 현재 위치 에서 가장 긴 체감 서열 수 를 구하 고 temp [i] 로 저장 하 는 것 이다.현재 의 최 장 체감 서브 시퀀스 는 이미 옮 겨 다 니 는 최 장 체감 서브 시퀀스 의 영향 을 받 아 시퀀스 헤드 에서 현재 위치의 이전 위치 로 옮 겨 다 니 며 하나씩 비교 합 니 다. a [j] 와 a [i] (현재 요소) 크기, temp 배열 을 업데이트 합 니 다.이러한 해법 시간 복잡 도 는? o（n^2）。

int LIS(int array[],int n)
{
    int temp[n];//             
    for(int i=0;i temp[i] )
		{
			temp[i] = temp[j] + 1;
		}
	}
    }
    return max(temp);
}

    최 장 단조 로 운 서열 은 동적 계획 이 해결 하 는 전형 적 인 문제 이다.지금 은 최 장 하강 서열 (엄격 한 하강) 을 예 로 들 어 O (nlogn) 로 어떻게 해결 하 는 지 설명 한다.문제 처리 대상 은 시퀀스 a [1. n] 입 니 다.전체 동적 계획 알고리즘 은 이렇게 실 현 됩 니 다.

procedure longest-decreasing-subsequence
begin
      ans ←0 //          
　　　for  i←1 to n do
　　　   begin
　　　          j←1,k←ans
　　　          while (j≤k) do
　　　              begin
　　　                   m ← (j+k) div 2
　　　                   if b[m]>a[i]  j←m+1
　　　                   else k←m-1
　　　              end
　　　         if j>ans  ans←ans+1
　　　         b[j]←a[i]
　　　   end
　　　return ans
end

    이 프로그램 은 매우 짧 고 간결 하 며, 그 중의 오묘 함 은 여전히 적지 않다.이 과정 을 이해 하기 위해 서 는 가장 기본 적 인 해결 방법 부터 분석 해 야 한다.
    우선 우 리 는 최 장 하강 서열 을 구 하 는 알고리즘 을 알 고 있다.
          a0 = + 무한대;
          M[0]=0;
          M[i]=MAX{M[j]+1,0<=ja[i]}
          P [i] = j (j 는 상기 식 에서 MAX 를 취 할 때의 j 값)
          ans=MAX{M[i]}
    이 공식 에서 P 는 결정 을 나 타 냈 다.이 P 를 전문 적 으로 고려 하면 여러 가지 결정 이 M [i] 의 최대 치 를 얻 을 수 있 습 니 다. 이런 결정 은 모두 등가 입 니 다 (예 를 들 어 배열 {9, 4, 3, 2, 9, 8, 7, 6, 10, 9} 에서 요소 10 전의 8 개 요소 중 서열 {9, 4, 3, 2} 과 {9, 8, 7, 6} 은 모두 단 조 롭 게 감소 하 는 4 개의 요소 입 니 다).그러면 우 리 는 당연히 P 에 대해 특별한 제한 을 할 수 있다. 즉, 모든 등가 의 결정 j 에서 P 는 체감 서열 중 마지막 요소 (즉 최소 요소) 중 가장 큰 것 을 선택 할 수 있다. (예 를 들 어 상기 예 에서 우 리 는 요소 6 을 선택한다. 왜냐하면 6 > 2).
    P 의 선택 은 우리 가 결 과 를 얻 은 것 과 아무런 관계 가 없 지만 P 에 대한 설명 은 이러한 문 제 를 설명 하고 자 한다. x 번 째 숫자 에 있어 서 길 이 는 M [x] 의 최 장 하강 서열 을 구성 할 수 있다. 그의 서브 문 제 는 a [1. x - 1] 중의 한 길이 가 M [x] - 1 의 최 장 하강 서열 이 고 이 서열 의 마지막 수 는 a [x] 보다 크다.우 리 는 P 에 게 이 모든 가능 한 해 중 끝 수가 가장 큰 것 을 선택 하 라 고 했다. 즉, a [1. x - 1] 을 처리 한 후에 모든 길이 가 M [x] - 1 인 하강 서열 에 대해 P [x] 의 결정 은 그 중에서 끝 이 가장 큰 것 과 만 관련 되 고 나머지 똑 같은 길이 의 서열 에 대해 우 리 는 관심 을 가 질 필요 가 없다.
이 를 통 해 알 수 있 듯 이 다른 동적 변화 하 는 배열 b 로 우리 가 a [x] 를 계산 한 후에 a [1. x] 에서 얻 은 모든 하락 서열 은 길이 에 따라 L 개의 등가 류 로 나 뉘 는데 모든 등가 류 에서 하나의 대표 만 필요 하 다. 이것 은 이 등가 류 에서 끝의 수가 가장 크 고 우 리 는 이 를 b [j], 1 ≤ j ≤ L 로 기록한다.b [j] 는 모든 길이 가 j 인 하강 서열 중 마지막 수가 가장 큰 그 서열 의 대표 이다.
    우 리 는 a [1. x - 1] 의 결 과 를 모두 b 에 기 록 했 기 때문에 현재 의 한 수 a [x] 를 처리 하고 우 리 는 앞의 a [j] (1 ≤ j ≤ x - 1) 와 비교 할 필요 가 없 으 며 b [j] (1 ≤ j ≤ L) 와 비교 해 야 한다.
    a [x] 의 처리 에 대해 우 리 는 간단하게 설명 한다.
    우선, a [x], 즉 a [1. x - 1] 에 길이 가 1 에서 L 인 하강 서열 만 존재 한다. 그 중에서 b [L] 은 길이 가 L 인 서열 의 대표 이다. a [x] 는 분명히 a [x] 를 이 서열 의 뒤에 연결 시 켜 길이 가 L + 1 인 서열 을 형성 했다. 이때 b [L + 1] = a [x], 즉 a [x] 는 길이 가 L + 1 인 서열 의 대표 로 서 L 은 1 을 증가 해 야 한다.
    다른 하 나 는 a [x] > = b [1] 일 수 있 습 니 다. 분명 한 것 은 이때 a [x] 는 a [1. x] 의 모든 요소 중에서 가장 큰 것 입 니 다. 이 는 길이 가 1 인 하강 서열 만 구성 할 수 있 고 반드시 가장 큰 것 이기 때문에 b [1] 의 대표 로 서 b [1] = a [x] 입 니 다.
    만약 앞의 상황 이 존재 하지 않 는 다 면 우 리 는 j, 2 ≤ j ≤ L, b [j - 1] > a [x], b [j] ≤ a [x] 를 찾 을 수 있 을 것 이다. 이때 분석 하면 a [x] 는 반드시 b [j - 1] 뒤에 연결 되 고 새로운 길 이 는 j 의 서열 이 될 것 이다. 이것 은 a [x] 가 그 어떠한 b [k] 뒤에 연결 되면 1 ≤ k < j - 1, 그러면 b [k + 1] > a [x], a [x] 가 대표 가 될 수 없 기 때문이다.[k] < = a [x], a [x] 는 이 서열 을 연장 할 수 없습니다. a [x] ≥ b [j] 이기 때문에 우 리 는 b [j] 를 a [x] 로 업데이트 합 니 다.
    어떤 상황 이 완 성 된 후에 b [1. L] 은 분명히 하락 한 서열 이지 만 길이 가 L 인 하강 서열 을 나타 내지 않 는 다 는 점 은 헷 갈 릴 수 없다.
    이 몇 가지 상황 은 실제 적 으로 a [x] 를 처리 하여 b [L + 1] 을 무한 소 로 하고 왼쪽 에서 오른쪽으로 첫 번 째 위치 j 를 찾 아 b [j] ≤ a [x] 를 찾 은 다음 에 b [j] = a [x] 를 j = L + 1 하면 L 이 동시에 증가한다. x 처 이전에 대응 하 는 최 장 하강 서열 의 길 이 는 M [x] = j 이다.
    이러한 프로그램 은 다음 과 같이 설명 합 니 다.

procedure longest-decreasing-subsequence’
begin
	L ←0
　　　for  x←1 to n do
　　　   begin
　　　		b[L+1]←   
			j←1
　　　　　　while (b[j]>a[x]) j←j+1
　　　　　　b[j]←a[x]
　　　　　　if j>L then L←j
　　　   end
　　　return L
end

    while 순환 부분 에 주의 하 십시오. 이것 은 퇴화 하기 쉽 습 니 다. a 자체 가 하강 서열 일 때 O (n2) 의 알고리즘 으로 퇴화 합 니 다.
    이때 우 리 는 이 절 에서 언급 한 이분법 을 이용 해 야 한다. 기울 임 꼴 부분 은 가장 작은 j 를 찾 아 b [j] ≤ a [x] 를 만족 시 키 는 것 이다. b [1. L] 은 단조 로 운 하강 의 질서 있 는 서열 이기 때문에 우 리 는 2 점 으로 이 위 치 를 찾 아야 한다. 그 원 리 는 이 진 트 리 에서 찾 는 것 과 같다. 그래서 우리 가 처음에 제시 한 고전 프로그램 세그먼트 가 생 겼 다. 그 관건 적 인 부분 은:

　　　j←1,k←ans
　　　          while (j≤k) do
　　　              begin
　　　                   m ← (j+k) div 2
　　　                   if b[m]>a[i] j←m+1
　　　                     else k←m-1
　　　              end
　　　         if j>ans  ans←ans+1
　　　         b[j]←a[i]

    이상 은 최 장 하강 서열 의 길 이 를 해 결 했 는데 사실은 상승 서열 을 해결 하거나 최 장 상승 서열 을 해결 하지 않 으 면 알고리즘 중의 부 등 호 를 약간 수정 하면 된다.
지금 우 리 는 배열 에서 가장 긴 체감 서브 시퀀스 의 길 이 를 찾 았 습 니 다. 그러면 이 서브 시퀀스 를 어떻게 출력 합 니까? 여기 서 먼저 구 덩이 를 파 서...
    이 문 제 는 또 재 미 있 는 점 이 있다. b 로 최 장 하강 서열 의 길 이 를 구 하 는 동시에 우 리 는 a 서열 에 대해 최소 하강 서열 로 덮어 쓰 는 구 조 를 완성 했다. 다시 말 하면 우 리 는 이 방법 을 통 해 한 서열 의 최소 커버 수 등 최 장 하강 서열 의 길 이 를 설명 할 수 있다. 이것 은 재 미 있 는 명제 이다.
예 를 들 어 시퀀스 {1,-1, 9,-3, 4,-5, 6, - 7} 구 하 는 최 장 체감 서브 시퀀스 는? {1, - 1, - 3, - 5, - 7}, 길이 가 5 이면 최소 5 개가 내 려 가지 않 고 덮어 써 야 합 니 다. {1} {- 1, 9} {- 3, 4} {- 5, 6} {- 7}.
C + + 예시 원본 첨부:

#include 
using namespace std;
 
/*         LIS
 *          30
 *DP + BinarySearch
*/
 
int MaxV[30]; /*     i+1（len）             */
int len;      /*             MaxV     */
 
/*   MaxV[i]     x         */
int BinSearch(int * MaxV, int size, int x)
{
    int left = 0, right = size-1;
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(MaxV[mid] <= x)
        {
            left = mid + 1;
        }
else
        {
            right = mid - 1;
        }
    }
    return left;
}
 
int LIS(int * arr, int size)
{
    MaxV[0] = arr[0]; /*     */
    len = 1;
    for(int i = 1; i < size; ++i) /*   arr[i]      LIS      */
    {
        if(arr[i] > MaxV[len-1]) /*            ，         */
        {
            MaxV[len++] = arr[i];
        }
else
        {
            int pos = BinSearch(MaxV,len,arr[i]);
            MaxV[pos] = arr[i];
        }
    }
    return len;
}
 
void main()
{
    int arr[] = {1,-1,2,-3,4,-5,6,-7};
 
    /*   LIS   */
    printf("%d
",LIS(arr,sizeof(arr)/sizeof(int)));
}

참고:
1、http://blog.csdn.net/tianshuai1111/article/details/7887810