파이썬에서 요소를 재배열하여 목록의 거듭제곱의 최대값을 얻는 프로그램

<시간/>

N개의 양수의 목록 번호가 있다고 가정합니다. 이제 목록에서 단일 값을 선택하고 임의의 위치로 이동(교환 아님)할 수 있습니다. 우리는 또한 위치로 전혀 이동할 수 없습니다. 그래서 우리는 목록의 가능한 최대 최종 거듭제곱이 얼마인지 찾아야만 합니까? 우리가 알고 있듯이 목록의 힘은 모든 인덱스 i에 대한 (index + 1) * value_at_index의 합입니다.

$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times 목록[i]$$

따라서 입력이 nums =[6, 2, 3]과 같으면 출력은 26이 됩니다. 6을 끝까지 이동하여 목록 [2, 3, 6]을 얻을 수 있으므로 거듭제곱은 다음과 같습니다. (2 * 1) + (3 * 2) + (6 * 3) =26.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

P :=값이 0인 목록
기본 :=0
각 인덱스 i와 A의 값 x에 대해 수행
- P의 끝에 P + x의 마지막 요소 삽입
- 기본 :=기본 + (i+1) * x
as :=기본
A의 각 인덱스 i와 값 x에 대해 수행
- 범위 0에서 A + 1까지의 j에 대해 수행
  - ans :=ans의 최대값 및 (base + P[i] - P[j] -(i - j) * x)
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, A):
      P = [0]
      base = 0
      for i, x in enumerate(A, 1):
         P.append(P[-1] + x)
         base += i * x
      ans = base
      for i, x in enumerate(A):
         for j in range(len(A) + 1):
            ans = max(ans, base + P[i] - P[j] - (i - j) * x)
      return ans
ob = Solution()
nums = [6, 2, 3]
print(ob.solve(nums))

입력

[6, 2, 3]