배열이 두 개 있다고 가정합니다. 증가하는 부분이 첫 번째 배열에서 나와야 하고 첫 번째 배열의 하위 시퀀스여야 하도록 가능한 가장 긴 비트 시퀀스를 찾아야 합니다. 비슷하게 감소하는 부분은 두 번째 배열과 두 번째 배열의 하위 시퀀스에서 가져와야 합니다.
따라서 입력이 A =[2, 6, 3, 5, 4, 6], B =[9, 7, 5, 8, 4, 3]인 경우 출력은 [2, 3, 4 , 6, 9, 7, 5, 4, 3]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
index_ceiling() 함수를 정의합니다. arr, T, 왼쪽, 오른쪽, 키가 필요합니다.
-
동안 오른쪽 - 왼쪽> 1, 수행
-
중간 :=왼쪽 +(오른쪽 - 왼쪽) / 2;
-
arr[T[mid]]>=키인 경우
-
오른쪽 :=중간
-
-
그렇지 않으면
-
왼쪽 :=중간
-
-
-
오른쪽으로 돌아가기
-
long_inc_seq() 함수를 정의합니다. A
-
n :=A의 크기
-
tails_idx :=n 크기의 배열, 0으로 채움
-
prev_idx :=크기가 n인 배열, -1로 채우기
-
길이 :=1
-
범위 1에서 n까지의 i에 대해 수행
-
A[i]
-
tails_idx[0] :=i
-
-
그렇지 않으면 A[i]> A[tails_idx[length - 1]]일 때
-
prev_idx[i] :=tails_idx[길이 - 1]
-
tails_idx[길이] :=i
-
길이 :=길이 + 1
-
-
그렇지 않으면
-
pos :=index_ceiling(A, tails_idx, -1, 길이 - 1, A[i])
-
prev_idx[i] :=tails_idx[pos - 1]
-
tails_idx[pos] :=i
-
-
-
i :=tails_idx[길이 - 1]
-
i>=0인 동안 수행
-
답변 끝에 A[i] 삽입
-
i :=prev_idx[i]
-
-
기본 방법에서 다음을 수행하십시오 -
-
n1 :=A의 크기, n2 :=B의 크기
-
long_inc_seq(A)
-
답변 :=역 답변
-
B :=역 B
-
long_inc_seq(B)
-
답변을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
answer = [] def index_ceiling(arr,T, left,right, key): while (right - left > 1): mid = left + (right - left) // 2; if (arr[T[mid]] >= key): right = mid else: left = mid return right def long_inc_seq(A): n = len(A) tails_idx = [0]*(n) prev_idx = [-1]*(n) length = 1 for i in range(1, n): if (A[i] < A[tails_idx[0]]): tails_idx[0] = i elif (A[i] > A[tails_idx[length - 1]]): prev_idx[i] = tails_idx[length - 1] tails_idx[length] = i length += 1 else: pos = index_ceiling(A, tails_idx, -1, length - 1, A[i]) prev_idx[i] = tails_idx[pos - 1] tails_idx[pos] = i i = tails_idx[length - 1] while(i >= 0): answer.append(A[i]) i = prev_idx[i] def long_bitonic(A,B): n1 = len(A) n2 = len(B) global answer long_inc_seq(A) answer = answer[::-1] B = B[::-1] long_inc_seq(B) A = [2, 6, 3, 5, 4, 6] B = [9, 7, 5, 8, 4, 3] long_bitonic(A,B) print(answer)
입력
[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]
출력
[2, 3, 4, 6, 9, 7, 5, 4, 3]