최고의 관광 쌍

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 <= 값[i] <= 1000

힌트:

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

해결책:

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

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

  
  
  설명:




초기화:



maxI는 인덱스 1부터 쌍을 평가하기 시작하므로 값[0]으로 초기화됩니다.

maxScore는 최대 점수를 추적하기 위해 0으로 초기화됩니다.



배열 반복:


1부터 시작하는 각 인덱스 j에 대해 다음 공식을 사용하여 (i, j) 쌍의 점수를 계산합니다.
점수 = 최대 I 값[j] - j

maxScore를 획득한 최대값으로 업데이트하세요.



maxI 업데이트:


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



최대 점수 반환:

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





  
  
  복잡성:




시간 복잡도: O(n) 왜냐하면 배열을 한 번만 반복하기 때문입니다.

공간 복잡도: O(1) 일정한 양의 공간을 사용하므로


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

연락처 링크

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

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


링크드인
깃허브



          

            
  

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