회전된 배열에서 주어진 길이의 연속 하위 배열의 최대 합을 찾는 쿼리용 JavaScript 프로그램

배열을 회전한다는 것은 숫자를 얻고 배열의 요소를 원형 순서에 따라 오른쪽이나 왼쪽으로 이동해야 함을 의미합니다. 여기서는 지정하지 않으므로 오른쪽 회전을 기준으로 하고, 주어진 회전 수 이후에는 합이 가장 큰 하위 배열을 반환합니다. 기사에서 올바른 설명과 함께 코드를 살펴보겠습니다.

문제 소개

이 문제에서는 정수를 포함하는 배열과 쿼리 쌍을 포함하는 또 다른 배열을 얻습니다. 쿼리 배열의 각 인덱스에는 두 개의 정수가 포함되어 있습니다. 첫 번째 정수는 현재 배열의 회전 수를 나타내고 두 번째 정수는 원하는 하위 배열의 길이를 나타냅니다. 예를 들어 -

주어진 배열이 [5, 7, 1, 4, 3, 8, 2]이고 쿼리는 다음과 같다면 -

으아아아

이 문제에 대한 해결책을 찾아보겠습니다

순진한 방법

가장 쉬운 방법은 두 개의 for 루프를 직접 사용하여 주어진 문제를 구현하는 것입니다. 먼저 배열 위로 이동하여 지정된 횟수만큼 시계 방향으로 회전합니다. 그런 다음 주어진 크기의 하위 배열과 가장 큰 합계를 갖는 하위 배열을 찾습니다. 코드를 살펴보겠습니다 -

예

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*D*N)입니다. 여기서 Q는 쿼리 수입니다. D는 원하는 각 하위 배열의 크기이고 N은 배열의 길이입니다.

위 코드의 공간 복잡도는 O(N)입니다. 회전된 배열을 저장하기 위해 추가 배열을 사용하기 때문입니다.

효율적인 방법

슬라이딩 윈도우 방식을 사용하면 이 문제를 효과적으로 해결할 수 있습니다. 이 질문의 코드로 직접 이동하여 이를 통해 개요를 살펴보겠습니다. -

예

으아아아

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*N)입니다. 여기서 Q는 쿼리 수이고 N은 배열 길이입니다.

위 코드의 공간 복잡도는 O(N)입니다. 회전된 배열을 저장하기 위해 추가 배열을 사용하기 때문입니다.

결론

이 튜토리얼에서는 회전된 배열에서 주어진 길이의 연속 하위 배열의 최대 합을 찾기 위해 쿼리하는 JavaScript 프로그램을 구현했습니다. 시간 복잡도가 O(N*Q*D)인 순진한 방법을 구현한 후 슬라이딩 윈도우 개념을 사용하여 O(N*Q) 시간 복잡도로 개선했지만 두 코드의 공간 복잡도는 O(N)과 동일합니다. .

위 내용은 회전된 배열에서 주어진 길이의 연속 하위 배열의 최대 합을 찾는 쿼리용 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!