주어진 배열의 모든 회전 중에서 i*arr의 최대 합계를 찾는 JavaScript 프로그램

이 기사에서는 주어진 배열의 모든 회전 중에서 i*arr[i]의 최대 합을 찾는 JavaScript 프로그램을 구현합니다. 여기서 i*arr[i]는 배열의 모든 요소에 현재 위치의 요소를 곱하여 그 합을 최대화한다는 의미입니다. 주어진 배열 요소를 왼쪽이나 오른쪽으로 회전하여 최대 답을 얻을 수 있습니다. 이 질문에 대해서는 완전한 코드와 자세한 설명을 제공하겠습니다.

문제 소개

이 질문에서는 배열이 주어집니다. 모든 요소에 해당 인덱스 번호를 곱한 다음 모든 요소의 합을 더하면 숫자를 얻게 됩니다. 한 번의 회전으로 가장 왼쪽 또는 가장 오른쪽 요소를 배열의 반대쪽으로 이동할 수 있으며 이로 인해 각 요소의 인덱스가 변경되고 배열을 여러 번 회전할 수 있습니다(그러나 회전 수가 배열의 길이를 변경하면 첫 번째 배열과 동일한 배열을 얻게 됩니다. 배열을 회전하면 요소의 인덱스와 i*arr[i]의 합을 변경할 수 있습니다.

우리는 두 가지 접근 방식으로 합을 최대화하려고 노력할 것입니다. 먼저 예를 살펴보겠습니다 −

으아악

첫 번째 회전에서 가장 높은 합계인 29를 얻는 것을 볼 수 있습니다.

방법

필요한 합계를 찾는 방법에는 두 가지가 있습니다. 두 가지 방법을 모두 살펴보겠습니다. -

방법 1은 순진한 접근 방식으로 O(N) 시간에 배열의 모든 회전을 찾고, 각 회전에 대해 배열을 순회하여 O(N) 시간에 모든 요소의 합을 구하지만 그렇지 않습니다. 추가 공간을 사용하십시오.

예

으아악

시간 복잡도와 공간 복잡도

위 코드의 시간 복잡도는 O(N*N)입니다. 여기서 N은 배열의 크기이고 위 코드의 공간 복잡도는 O(1)입니다.

각 반복마다 마지막 요소에 대한 단일 요소의 차이만 있습니다. 그 이유는 해당 요소가 배열 길이에서 업데이트되기 때문입니다. 다른 요소의 경우 1에서 0으로 요소가 하나 더 추가되므로 다음과 같이 코드를 작성할 수 있습니다. −

예

으아악

시간 복잡도와 공간 복잡도

위 코드의 시간 복잡도는 O(N)입니다. 여기서 N은 배열의 크기이고 위 코드의 공간 복잡도는 O(1)입니다. 이 접근 방식은 이전 접근 방식에 비해 매우 좋습니다.

결론

이 튜토리얼에서는 주어진 배열의 모든 회전 중에서 i*arr[i]의 최대 합을 찾는 JavaScript 프로그램을 구현했습니다. 우리는 두 가지 방법을 보았습니다. 하나는 주어진 배열의 모든 회전을 찾은 다음 i*arr[i] 표현식의 결과를 비교하는 것입니다. 두 번째 방법에서는 수학적 방법을 사용하여 시간 복잡도를 O(N*N)에서 O(N)으로 줄입니다.

위 내용은 주어진 배열의 모든 회전 중에서 i*arr의 최대 합계를 찾는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!