. 겹치는 하위 배열의 최대 합계-PHP 튜토리얼-php.cn

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

Barbara Streisand

풀어 주다： 2024-12-30 10:24:10

원래의

1029명이 탐색했습니다.

. Maximum Sum of on-Overlapping Subarrays

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 <= nums.length <= 2 * 10⁴
1 <= 숫자[i] < 2¹⁶
1 <= k <= 층(nums.length / 3)

해결책:

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

접근하다:

길이가 k인 하위 배열의 합을 미리 계산합니다.
먼저 입력 배열 nums에서 길이가 k인 모든 하위 배열의 합을 계산합니다. 이는 슬라이딩 윈도우 기술을 사용하여 선형 시간에 효율적으로 수행할 수 있습니다.
동적 프로그래밍(DP):
현재 위치까지 찾은 최상의 하위 배열의 인덱스를 저장하기 위해 왼쪽과 오른쪽에 두 개의 보조 배열을 만듭니다. left[i]는 인덱스 i 이전에 끝나는 가장 좋은 하위 배열의 인덱스를 저장하고, right[i]는 인덱스 i 이후부터 시작하는 가장 좋은 하위 배열의 인덱스를 저장합니다.
최대 합계 반복 및 계산:
인덱스 j에서 시작하는 가능한 각 중간 하위 배열에 대해 j 이전의 가장 좋은 왼쪽 하위 배열과 j 이후의 가장 좋은 오른쪽 하위 배열을 고려하여 총합을 계산합니다.
사전순 정렬:
동일한 합으로 유효한 답변이 여러 개 있는 경우 사전순으로 가장 작은 답변을 반환합니다. 이는 반복 순서에 따라 보장됩니다.

이 솔루션을 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]
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li>
<p><strong>하위 배열 합계 계산:</strong></p>

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

<ul>
<li>
left[i]는 인덱스 i 앞에서 끝나는 최대 합계를 갖는 하위 배열의 인덱스를 보유합니다.</li>
<li>
right[i]는 인덱스 i 이후부터 시작하는 최대 합계를 갖는 하위 배열의 인덱스를 보유합니다.</li>
</ul>
</li>
<li>
<p><strong>최종 계산:</strong></p>

<ul>
<li>각 중간 하위 배열 j에 대해 가장 좋은 왼쪽 하위 배열과 가장 좋은 오른쪽 하위 배열의 조합을 확인하고 그 합이 현재 최대값보다 큰 경우 결과를 업데이트합니다.</li>
</ul>
</li>
<li>
<p><strong>사전순으로 가장 작은 답변:</strong></p>

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

<h3>
  
  
  예:
</h3>

<p>입력:<br>
</p>

<pre class="brush:php;toolbar:false">$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

로그인 후 복사

출력은 다음과 같습니다.