나는 그레이트 매트릭스다

1975. 최대 행렬 합

난이도:중

주제: 배열, 탐욕, 매트릭스

n x n 정수 행렬이 주어졌습니다. 다음 작업은 여러 번 수행할 수 있습니다.

• 행렬의 인접 요소 두 개를 선택하고 각 요소에 -1을 곱하세요.

두 요소가 경계를 공유하는 경우에만 인접한 것으로 간주됩니다.

귀하의 목표는 행렬 요소의 합을 최대화하는 것입니다. 위에서 언급한 연산을 사용하여 행렬 요소의 최대합을 반환합니다.

예 1:

• 입력: 행렬 = [[1,-1],[-1,1]]
• 출력: 4
• 설명: 다음 단계에 따라 합계가 4가 되도록 할 수 있습니다.
  • 첫 번째 행의 2개 요소에 -1을 곱합니다.
  • 첫 번째 열의 2개 요소에 -1을 곱합니다.

예 2:

• 입력: 행렬 = [[1,2,3],[-1,-2,-3],[1,2,3]]
• 출력: 16
• 설명: 다음 단계에 따라 합계가 16이 되도록 할 수 있습니다.
  • 두 번째 행의 마지막 요소 2개에 -1을 곱합니다.

제약조건:

• n == 행렬.길이 == 행렬[i].길이
• 2
• -10⁵ <= 행렬[i][j] <= 10⁵

힌트:

1. 각 행에 음수가 하나만 포함되도록 연산을 사용해 보세요.
2. 부정 요소가 하나만 있는 경우 긍정적 요소로 변환할 수 없습니다.

해결책:

연산을 사용하여 행렬의 합을 최대화하려면 합에 대한 음의 기여도의 절대값을 최소화해야 합니다. 계획은 다음과 같습니다.

1. 음수 계산: 행렬에 얼마나 많은 음수가 있는지 추적합니다.
2. 최소 절대값 찾기: 행렬에서 가장 작은 절대값을 결정합니다. 이는 음수가 홀수인 경우에 도움이 됩니다.
3. 홀수 음수 조정: 음수의 개수가 홀수이면 가장 작은 절대값을 양수로 바꿀 수 없으며 이로 인해 가능한 최대 합계가 제한됩니다.

이 솔루션을 PHP로 구현해 보겠습니다: 1975. 최대 행렬 합

  
  
  설명:




절대값의 합: 최적의 구성은 가능한 한 많은 음수를 양수로 바꾸므로 모든 요소의 절대값의 합을 계산합니다.

가장 작은 절대값 추적: 음수의 개수가 홀수일 때 합계를 조정하는 데 사용합니다.

홀수 음수 처리: 음수를 완전히 중화할 수 없는 경우 피할 수 없는 음수 요소를 설명하기 위해 합계에서 가장 작은 절대값의 두 배를 뺍니다.



  
  
  복잡성




시간 복잡도: O(n^2), 행렬이 한 번 탐색되기 때문입니다.

공간 복잡도: O(1), 변수 외에 추가 공간이 사용되지 않기 때문입니다.


이 솔루션은 주어진 제약 내에서 효율적으로 작동합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 나는 그레이트 매트릭스다의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!