동적 프로그래밍을 사용하여 각 배열에서 가장 긴 이중음 시퀀스를 찾습니다. 이음 수열은 처음에는 증가한 다음 감소하는 수열입니다. 가장 긴 쌍음 시퀀스를 찾기 위해 2단계 접근 방식을 사용합니다. 먼저, 주어진 배열에서 가장 긴 증가 부분 수열을 찾은 다음, 주어진 배열의 역순으로 가장 긴 감소 부분 수열을 찾습니다. 마지막으로 두 하위 시퀀스의 길이를 더하고 1을 빼서 중간에 있는 공통 요소를 제외합니다.
바이톤 수열은 처음에는 증가한 다음 감소하는 수열입니다. 주어진 배열에서 가장 긴 바이토널 시퀀스를 찾는 방법은 동적 프로그래밍을 사용하는 것입니다.
두 개의 배열 "inc"와 "dec"를 초기화하여 각 인덱스에서 끝나는 가장 긴 증가 하위 시퀀스의 길이를 저장합니다.
이전 인덱스의 값을 사용하여 각 인덱스의 "inc" 및 "dec" 값을 업데이트하면서 배열을 반복합니다.
각 인덱스에서 "inc"와 "dec"의 합에서 1을 뺀 최대값을 찾습니다. 이렇게 하면 해당 인덱스를 포함하는 가장 긴 비트 증가 하위 시퀀스의 길이가 제공됩니다.
3단계에서 찾은 최대값을 가장 긴 비트 증가 하위 시퀀스의 길이로 반환합니다.
가장 긴 비트 시퀀스를 재구성하려면 "inc" 및 "dec"의 값을 사용하여 3단계에서 최대값을 제공한 인덱스부터 시작하여 역추적합니다.
재구성된 시퀀스를 가장 긴 이중음 시퀀스로 반환합니다.
다음은 동적 프로그래밍을 사용하여 가장 긴 바이토닉 하위 시퀀스를 찾는 JavaScript 프로그램의 완전한 작업 예입니다 −
으아악첫 번째 단계는 입력 배열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 중국어 웹사이트의 기타 관련 기사를 참조하세요!