최 장자 서열

전환: 클릭 하여 링크 를 열 면 가장 긴 하위 서열 은 동적 계획 을 접 한 사람 이 자주 만 나 도 해결 해 야 하 는 문제 라 고 할 수 있 습 니 다. 가장 흔히 볼 수 있 는 것 은 두 가지 가 있 습 니 다. 하 나 는 가장 긴 공공 하위 서열 (LCS) 이 고 다른 하 나 는 가장 긴 상승 하위 서열 (LIS) 입 니 다.오늘 나 는 이 두 가지 방법 을 총 결 해 보 겠 다.
1: 최 장 공통 하위 시퀀스 (LCS)
제목 설명: 두 개의 배열 을 드 리 겠 습 니 다. 숫자 일 수도 있 고 문자열 일 수도 있 습 니 다. 우 리 는 숫자 라 고 가정 합 니 다!예 를 들 어:
　　　　X  =  1, 5, 6, 4, 1, 3, 7
　　　　Y  =  1, 1, 6, 8, 3, 4, 7
새로운 배열 S 를 구 합 니 다. 이 배열 의 모든 수 는 X 와 Y 배열 의 공공 수 이 고 원래 배열 의 숫자의 전후 관 계 를 만족 시 킵 니 다. 이런 배열 은 여러 가지 가 있 습 니 다. 예 를 들 어 (1, 1, 1, 3, 7), (1, 6, 7) 등 이 있 습 니 다.동시에 S 배열 의 길이 가 가장 긴 것 은 위의 것 (1, 1, 3, 7) 과 같 고 길이 가 4 라면 바로 답 을 구 하 는 것 입 니 다!
DP 문 제 를 푸 는 데 있어 서 가장 중요 한 것 은 DP 함 수 를 정확하게 구성 할 수 있다 는 것 이다. 잘 구성 할 수 있다 면 반 은 성공 할 것 이다.
dp [i] [j] 는 X 배열 의 앞 i 비트 와 Y 배열 의 앞 j 비트 이전의 LCS 를 표시 합 니 다. 그러면 앞의 세 상태 에서 밀어 낼 수 있 습 니 다.
　　　0                                    if (i = 0 | j = 0) -- 초기 화, 이해 하기 어렵 지 않 습 니 다. X 든 Y 배열 이 든 길이 가 0 이면 S 배열 은 0 입 니 다.
　　　dp[i][j] = max(dp[i-1][j],dp[i][j-1]    if (i, j > 0 & & X [i]! = Y [j]) - S 배열 에 숫자 를 추가 하지 않 으 면 앞에서 만 계승 할 수 있 습 니 다. 하 나 는 X 에서, 하 나 는 Y 에서, 하 나 는 Y 에서 만 볼 수 있 습 니 다.
　　　dp[i-1][j-1] + 1              if (i, j > 0 & & X [i] = Y [j]) -- 두 개가 같다 면 당연히 S 수 조 를 1 로 더 하면 X 와 Y 가 모두 계승 한 것 으로 볼 수 있다
코드 는 간단 합 니 다. for 두 개 를 순환 하면 됩 니 다.
2: 최 장 서브 시퀀스 (LIS)
제목 설명: X 배열, X = 1, 2, 3, 6, 5, 7, 4, 8, 6 같은 배열 을 드 리 겠 습 니 다.
새로운 배열 S 를 구 합 니 다. 이 배열 의 모든 수 는 X 배열 의 수 이 고 S 중의 임 의 두 개의 수 S [i], S [j] 는 j > i & s [j] > s [i] 를 만족 시 킵 니 다. 또한 S 배열 이 가장 긴 것 은 (1, 2, 3, 6, 7, 8) 과 (1, 2, 3, 5, 7, 8), 길 이 는 6 입 니 다.
dp [i] 는 X 배열 의 i 번 째 요 소 를 S 배열 의 기본 요소 로 하 는 가장 긴 하위 서열 의 길 이 를 나타 낸다. 그러면 하위 문제 로 해결 할 수 있다.
　　dp[i] = max(dp[j]) + 1    0 num [j]. i 앞에서 조건 에 맞 는 최 장자 서열 을 찾 는 것 입 니 다.
    이 문제 에 대해 말하자면 dp 방정식 은 비교적 쉽게 추측 하고 이해 할 수 있 지만, 시간 복잡 도 는 O (n ^ 2) 인 것 을 발견 할 수 있다. 이것 은 많은 문제 에 대해 받 아들 일 수 없 기 때문에 최적화 해 야 한다. 이것 은 하나의 문제 와 관련 되 고, 가장 긴 서브 시퀀스 의 O (n * lgn) 방법 이다.
    방법 은 다음 과 같 습 니 다. 먼저 배열 stack 을 드 리 겠 습 니 다. 가장 긴 증가 서브 시퀀스 (증가 하 는 요구 에 따라 배열 의 맨 위 에 있 는 숫자 가 가장 크 고 맨 끝 에 있 는 숫자 가 가장 적 습 니 다. 스 택 을 사용 하면 더 잘 이해 할 수 있 습 니 다) 를 저장 하고 X 배열 을 스 캔 합 니 다. 만약 에 X [i] 가 배열 의 맨 위 에 있 는 요소 (최대 값) 보다 크 면그러면 이 수 를 stack 배열 에 넣 으 세 요. 상단 요소 보다 작 으 면 stack 배열 에서 X [i] 보다 큰 첫 번 째 수 를 찾 고 X [i] 로 교체 하 세 요. stack 배열 은 질서 가 있 기 때문에 첫 번 째 X [i] 보다 큰 수 를 찾 을 때 2 점 으로 찾 아 할 수 있 습 니 다. 이것 이 최적화 입 니 다!
    이 두 가 지 는 모두 매우 간단 한 dp 문제 이지 만 동태 기획 사상 도 포함 되 어 있 습 니 다. 뒤의 많은 문제 에서 당신 은 이런 사상 을 무심코 사용 하 는 것 을 발견 할 수 있 기 때문에 그들 을 잘 이해 하 는 것 이 필요 합 니 다. 그러나 동태 계획 이 넓 고 심오 합 니 다. 그 는 고정된 순서 가 없 기 때문에 많은 것 이 사상 이기 때문에 이 두 가지 만 으로 는 부족 합 니 다!
O (n ^ 2) 의 알고리즘:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;
const int maxn = 1010;
int n;
int array[maxn], maxv[maxn], lis[maxn];
int main(){
    scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &array[i]);
		lis[i] = 1;
	}
	lis[0] = -1;

	maxv[1] = array[1];
	maxv[0] = INT_MIN;
	int maxlis = 1;

	for(int i = 1; i <= n; i++)
	{
		int j;//mav[i]     i                   
		for(j = maxlis; j >= 1; j--)
		{
			if(array[i] > maxv[j])
			{
				lis[i] = j + 1;
				break;
			}
		}
		if(lis[i] > maxlis){
			maxlis = lis[i];
			maxv[maxlis] = array[i];
		}
		else if(maxv[j] < array[i] && array[i] < maxv[j + 1])
		{
			maxv[j + 1] = array[i];
		}
	}
	printf("%d
", maxlis);
		return 0;
}

for(j = maxlis; j >= 0; j--)   {    if(array[i] > maxv[j])    {     lis[i] = j + 1;     break;    }   } 그 j 를 구 할 때 2 분 검색 으로 검색 하면 O (n ^ 2) 를 O (nlogn) 로 낮 출 수 있 습 니 다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;

const int maxn = 1010;
int n;
int array[maxn], maxv[maxn], lis[maxn];

int binarysearch(int low, int high, int index);

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &array[i]);
		lis[i] = 1;
	}
	lis[0] = -1;
	maxv[1] = array[1];
	maxv[0] = INT_MIN;
	int maxlis = 1;
	for(int i = 1; i <= n; i++)
	{ 
		int j = binarysearch(1, maxlis, i);//                     array[i]。
		if(j != -1)
			lis[i] = j + 1;
		else
			j = 0;
		if(lis[i] > maxlis)
		{
			maxlis = lis[i];
			maxv[maxlis] = array[i];
		}
		else if(maxv[j] < array[i] && array[i] < maxv[j + 1])
		{
			maxv[j + 1] = array[i];
		}
	}
	printf("%d
", maxlis);
		return 0;
}

int binarysearch(int low, int high, int index)
{
	int pre = -1;
	while(low <= high)
	{
		int mid = (low + high) >> 1;
		if(array[index] > maxv[mid])
		{
			pre = mid;
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	return pre;
}