Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 주어진 배열 표현식의 최대값을 찾는 프로그램

두 개의 정수 배열 nums와 values가 있다고 가정해 봅시다. 두 배열의 길이는 서로 같으며, nums의 원소들은 엄격하게 오름차순으로 정렬되어 있습니다. 이때 인덱스 쌍 i, j(단, i ≤ j)에 대해 다음 수식의 값 v를 최대화하는 것이 목표입니다.

v = values[i] + values[j] + nums[j] - nums[i]

예를 들어 nums = [1, 2, 7], values = [-4, 6, 5]가 입력으로 주어지면 정답은 16입니다. i = 1, j = 2를 선택하면 6 + 5 + 7 − 2 = 16이 되기 때문입니다.

접근 방법

주어진 수식을 항별로 묶어 다시 써 보면 문제가 훨씬 단순해집니다.

v = (values[j] + nums[j]) + (values[i] - nums[i])

첫 번째 괄호 안의 식은 인덱스 j에만 의존하고, 두 번째 괄호 안의 식은 인덱스 i에만 의존합니다. 따라서 배열을 한 번만 순회하면서 각 인덱스에서 두 식의 최대값을 각각 추적한 뒤, 두 값을 더하면 정답을 구할 수 있습니다. 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.

알고리즘 단계

  • ans1과 ans2를 음의 무한대(-inf)로 초기화합니다.
  • i를 0부터 nums의 길이 - 1까지 순회하며 다음을 수행합니다.
    • ans1을 ans1과 values[i] - nums[i] 중 더 큰 값으로 갱신합니다.
    • ans2를 ans2와 values[i] + nums[i] 중 더 큰 값으로 갱신합니다.
  • ans1 + ans2를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 동작 과정을 더 잘 이해해 보겠습니다.

from math import inf

def solve(nums, values):
   ans1 = -inf
   ans2 = -inf
   for i in range(len(nums)):
      ans1 = max(ans1, (values[i] - nums[i]))
      ans2 = max(ans2, (values[i] + nums[i]))
   return ans1 + ans2

nums = [1, 2, 7]
values = [-4, 6, 5]
print(solve(nums, values))

입력

[1, 2, 7], [-4, 6, 5]

출력

16