. 겹치는 하위 배열의 최대 합계

689. 겹치지 않는 하위 배열 3개의 최대 합

난이도:어려움

주제: 배열, 동적 프로그래밍

정수 배열 nums와 정수 k가 주어지면 최대 합계를 갖는 길이 k의 겹치지 않는 하위 배열 3개를 찾아서 반환합니다.

각 간격의 시작 위치를 나타내는 인덱스 목록(0-인덱스)으로 결과를 반환합니다. 답변이 여러 개인 경우 사전순으로 가장 작은 답변을 반환합니다.

예 1:

• 입력: nums = [1,2,1,2,6,7,5,1], k = 2
• 출력: [0,3,5]
• 설명: 하위 배열 [1, 2], [2, 6], [7, 5]는 시작 인덱스 [0, 3, 5]에 해당합니다.
  • [2, 1]을 사용할 수도 있지만 [1, 3, 5]의 답은 사전순으로 더 큽니다.

예 2:

• 입력: nums = [1,2,1,2,1,2,1,2,1], k = 2
• 출력: [0,2,4]

제약조건:

• 1 4
• 1 16
• 1

해결책:

동적 프로그래밍 방식을 사용하겠습니다. 문제를 더 작은 하위 문제로 나누고 하위 배열의 중첩을 활용하여 길이가 k인 겹치지 않는 하위 배열 3개의 최대 합을 효율적으로 계산하는 것이 아이디어입니다.

접근하다:

1. 길이가 k인 하위 배열의 합을 미리 계산합니다.
   먼저 입력 배열 nums에서 길이가 k인 모든 하위 배열의 합을 계산합니다. 이는 슬라이딩 윈도우 기술을 사용하여 선형 시간에 효율적으로 수행할 수 있습니다.

2. 동적 프로그래밍(DP):
   현재 위치까지 찾은 최상의 하위 배열의 인덱스를 저장하기 위해 왼쪽과 오른쪽에 두 개의 보조 배열을 만듭니다. left[i]는 인덱스 i 이전에 끝나는 가장 좋은 하위 배열의 인덱스를 저장하고, right[i]는 인덱스 i 이후부터 시작하는 가장 좋은 하위 배열의 인덱스를 저장합니다.

3. 최대 합계 반복 및 계산:
   인덱스 j에서 시작하는 가능한 각 중간 하위 배열에 대해 j 이전의 가장 좋은 왼쪽 하위 배열과 j 이후의 가장 좋은 오른쪽 하위 배열을 고려하여 총합을 계산합니다.

4. 사전순 정렬:
   동일한 합으로 유효한 답변이 여러 개 있는 경우 사전순으로 가장 작은 답변을 반환합니다. 이는 반복 순서에 따라 보장됩니다.

이 솔루션을 PHP로 구현해 보겠습니다. 689. 겹치지 않는 하위 배열 3개의 최대 합

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>

설명:

1. 하위 배열 합계 계산:

   • 길이 k인 모든 가능한 하위 배열의 합을 계산합니다. 이는 먼저 처음 k개 요소의 합을 계산하여 수행됩니다. 그런 다음 각 후속 위치에 대해 남겨진 요소를 빼고 배열의 다음 요소를 추가하여 효율적인 슬라이딩 윈도우 접근 방식을 만듭니다.

2. 왼쪽 및 오른쪽 배열:

   • left[i]는 인덱스 i 앞에서 끝나는 최대 합계를 갖는 하위 배열의 인덱스를 보유합니다.
   • right[i]는 인덱스 i 이후부터 시작하는 최대 합계를 갖는 하위 배열의 인덱스를 보유합니다.

3. 최종 계산:

   • 각 중간 하위 배열 j에 대해 가장 좋은 왼쪽 하위 배열과 가장 좋은 오른쪽 하위 배열의 조합을 확인하고 그 합이 현재 최대값보다 큰 경우 결과를 업데이트합니다.

4. 사전순으로 가장 작은 답변:

   • 왼쪽에서 오른쪽으로 반복하면서 최대 합계를 산출하는 첫 번째 하위 배열을 자연스럽게 선택하여 사전식으로 가장 작은 솔루션을 보장합니다.

예:

입력:

$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

출력은 다음과 같습니다.

[0, 3, 5]

이 접근 방식을 사용하면 시간 복잡도가 대략 O(n)(여기서 n은 입력 배열 nums의 길이임)으로 효율적으로 유지됩니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 겹치는 하위 배열의 최대 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!