숫자 목록이 있다고 가정합니다. 가장 긴 bitonic 부분 시퀀스의 길이를 찾아야 합니다. Aswe 매듭 시퀀스는 엄격하게 증가했다가 엄격하게 감소하는 경우 바이토닉(bitonic)이라고 합니다. 엄격하게 증가하는 시퀀스는 bitonic입니다. 또는 엄격하게 감소하는 시퀀스도 bitonic입니다.
따라서 입력이 nums =[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 시퀀스 크기 16과 같으면 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
incrementalSubSeq :=주어진 배열 크기의 새로운 배열, 1로 채움
-
initialize i :=1의 경우 i <크기일 때 업데이트(i 1만큼 증가), −
-
j:=0 초기화의 경우, j
-
arr[i]> arr[j] 및 증가하는SubSeq[i] <증가하는SubSeq[j] + 1이면 -
-
증가SubSeq[i] :=증가SubSeq[j] + 1
-
-
*decreasingSubSeq :=주어진 배열 크기의 새로운 배열, 1로 채움
-
-
initialize i :=size - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
-
j 초기화의 경우:=크기 - 1, j> i일 때 업데이트(j를 1만큼 감소), −
-
arr[i]> arr[j] 및 reductionSubSeq[i]
-
reductionSubSeq[i] :=reductionSubSeq[j] + 1
-
-
최대 :=증가SubSeq[0] + 감소SubSeq[0] - 1
-
-
initialize i :=1의 경우 i <크기일 때 업데이트(i 1만큼 증가), −
-
증가하는SubSeq[i] + 감소하는SubSeq[i] - 1> 최대인 경우:
-
최대 :=incrementingSubSeq[i] + reductionSubSeq[i] - 1
-
-
최대 반환
-
-
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include<iostream>
using namespace std;
int longBitonicSub( int arr[], int size ) {
int *increasingSubSeq = new int[size];
for (int i = 0; i < size; i++)
increasingSubSeq[i] = 1;
for (int i = 1; i < size; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && increasingSubSeq[i] <
increasingSubSeq[j] + 1)
increasingSubSeq[i] = increasingSubSeq[j] + 1;
int *decreasingSubSeq = new int [size];
for (int i = 0; i < size; i++)
decreasingSubSeq[i] = 1;
for (int i = size-2; i >= 0; i--)
for (int j = size-1; j > i; j--)
if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
for (int i = 1; i < size; i++)
if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
return max;
}
int main() {
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int n = 16;
cout << longBitonicSub(arr, n);
} 입력
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16
출력
7