가장 긴 이중 모드 하위 시퀀스를 찾는 JavaScript 프로그램 |

동적 프로그래밍을 사용하여 각 배열에서 가장 긴 이중음 시퀀스를 찾습니다. 이음 수열은 처음에는 증가한 다음 감소하는 수열입니다. 가장 긴 쌍음 시퀀스를 찾기 위해 2단계 접근 방식을 사용합니다. 먼저, 주어진 배열에서 가장 긴 증가 부분 수열을 찾은 다음, 주어진 배열의 역순으로 가장 긴 감소 부분 수열을 찾습니다. 마지막으로 두 하위 시퀀스의 길이를 더하고 1을 빼서 중간에 있는 공통 요소를 제외합니다.

방법

바이톤 수열은 처음에는 증가한 다음 감소하는 수열입니다. 주어진 배열에서 가장 긴 바이토널 시퀀스를 찾는 방법은 동적 프로그래밍을 사용하는 것입니다.

• 두 개의 배열 "inc"와 "dec"를 초기화하여 각 인덱스에서 끝나는 가장 긴 증가 하위 시퀀스의 길이를 저장합니다.

• 이전 인덱스의 값을 사용하여 각 인덱스의 "inc" 및 "dec" 값을 업데이트하면서 배열을 반복합니다.

• 각 인덱스에서 "inc"와 "dec"의 합에서 1을 뺀 최대값을 찾습니다. 이렇게 하면 해당 인덱스를 포함하는 가장 긴 비트 증가 하위 시퀀스의 길이가 제공됩니다.

• 3단계에서 찾은 최대값을 가장 긴 비트 증가 하위 시퀀스의 길이로 반환합니다.

• 가장 긴 비트 시퀀스를 재구성하려면 "inc" 및 "dec"의 값을 사용하여 3단계에서 최대값을 제공한 인덱스부터 시작하여 역추적합니다.

• 재구성된 시퀀스를 가장 긴 이중음 시퀀스로 반환합니다.

Example

의 중국어 번역은

Example

입니다.

다음은 동적 프로그래밍을 사용하여 가장 긴 바이토닉 하위 시퀀스를 찾는 JavaScript 프로그램의 완전한 작업 예입니다 −

으아악

Explanation

의 중국어 번역은

Explanation

입니다.

• 첫 번째 단계는 입력 배열 arr 과 길이가 같고 1로 채워진 두 개의 배열 lis 및 lds을 초기화하는 것입니다. lis 는 "가장 긴 증가 부분 수열"을 나타내고, lds 는 "가장 긴 감소 부분 수열"을 나타냅니다.

• 다음 단계는 arr[i]로 끝나는 가장 긴 증가 부분 수열의 길이인 lis[i]를 계산하는 것입니다. 이는 j 범위가 0에서 i-1인 중첩 루프를 통해 달성됩니다. arr[i] > arr[j]이면 lis[i]를 현재 값과 최대값 lis[j] + 1으로 업데이트합니다.

• 다음 단계는 arr[i]에서 시작하는 가장 긴 감소 부분 수열의 길이인 lds[i]를 계산하는 것입니다. 이는 j 범위가 n-1에서 i+1인 중첩 루프를 통해 수행됩니다. arr[i] > arr[j]이면 lds[i]를 현재 값과 lds[j] + 1의 최대값으로 업데이트합니다.

• 마지막으로 입력 배열의 n 요소를 반복하여 lis[i] + lds[i] - 1의 최대값을 찾습니다. 이는 arr[i]로 끝나고 시작하는 최대값을 나타냅니다. 긴 비트 시퀀스의 길이입니다. 이 값은 maxLength 변수에 저장됩니다.

• 이 함수는 입력 배열에서 가장 긴 비트 증가 하위 시퀀스의 길이인 maxLength를 반환합니다.

위 내용은 가장 긴 이중 모드 하위 시퀀스를 찾는 JavaScript 프로그램 |의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!