최고의 관광 쌍

1014. 최고의 관광쌍

난이도:중

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

values[i]가 i^번째 관광지의 값을 나타내는 정수 배열 값이 제공됩니다. 두 관광지 i와 j 사이에는 j - i 거리가 있습니다.

관광지 쌍(i

반환두 관광지의 최대 점수.

예 1:

• 입력: 값 = [8,1,5,2,6]
• 출력: 11
• 설명: i = 0, j = 2, 값[i] 값[j] i - j = 8 5 0 - 2 = 11

예 2:

• 입력: 값 = [1,2]
• 출력: 2

제약조건:

• 2 4
• 1

힌트:

1. 한 번의 패스로(예: 입력을 반복하면서) 가장 좋은 관광지를 알 수 있습니까? 이를 위해 반복할 때 무엇을 저장하거나 추적해야 합니까?

해결책:

선형 시간 복잡도 O(n)을 사용하여 단일 패스 접근 방식을 사용할 수 있습니다. 아이디어는 배열을 반복하면서 가능한 최상의 값[i] i을 추적하는 것입니다. 이를 통해 모든 유효한 쌍(i, j)에 대해 점수 값[i] 값[j] i - j를 최대화할 수 있습니다.

이 솔루션을 PHP로 구현해 보겠습니다. 1014. 최우수 관광쌍

<?php /**
 * @param Integer[] $values
 * @return Integer
 */
function maxScoreSightseeingPair($values) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$values1 = [8, 1, 5, 2, 6];
echo maxScoreSightseeingPair($values1); // Output: 11

$values2 = [1, 2];
echo maxScoreSightseeingPair($values2); // Output: 2
?>

설명:

1. 초기화:

   • maxI는 인덱스 1부터 쌍을 평가하기 시작하므로 값[0]으로 초기화됩니다.
   • maxScore는 최대 점수를 추적하기 위해 0으로 초기화됩니다.

2. 배열 반복:

   • 1부터 시작하는 각 인덱스 j에 대해 다음 공식을 사용하여 (i, j) 쌍의 점수를 계산합니다. 점수 = 최대 I 값[j] - j
   • maxScore를 획득한 최대값으로 업데이트하세요.

3. maxI 업데이트:

   • 다음 반복에서 가능한 최대 값[i] i를 추적하려면 maxI를 업데이트하세요.

4. 최대 점수 반환:

   • 배열을 반복한 후 maxScore에는 모든 쌍의 최대 점수가 포함됩니다.

복잡성:

• 시간 복잡도: O(n) 왜냐하면 배열을 한 번만 반복하기 때문입니다.
• 공간 복잡도: O(1) 일정한 양의 공간을 사용하므로

이 솔루션은 제약 조건을 준수하면서 최대 점수를 효율적으로 계산하며 대규모 입력에 최적화되어 있습니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 최고의 관광 쌍의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!