파이썬에서 목록의 최대 최종 거듭제곱을 찾는 프로그램

<시간/>

목록이 있고 목록의 힘이 모든 인덱스에 대한 (index + 1) * value_at_index의 합으로 정의된다고 가정합니다. 또는 다음과 같이 나타낼 수 있습니다. -

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

이제 N개의 양의 정수가 있는 목록 번호가 있습니다. 목록에서 단일 값을 선택하고 임의의 위치로(교환하지 않음) 이동할 수 있습니다. 목록의 시작 또는 끝으로 이동할 수 있습니다. 또한 위치를 전혀 이동하지 않도록 선택할 수도 있습니다. 우리는 목록의 가능한 최대 최종 거듭제곱을 찾아야 합니다. 결과는 10^9 + 7로 수정되어야 합니다.

따라서 입력이 nums =[4, 2, 1]과 같으면 출력은 16이 됩니다.

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

피 :=[0]
기본 :=0
각 i, 인덱스 i의 x 및 A, 1의 항목 x에 대해 수행
- P의 끝에 P[-1] + x 삽입
- 기본 :=기본 + i * x
eval_at() 함수를 정의합니다. j, x
가 걸립니다.
- 반환 -j * x + P[j]
Intersection() 함수를 정의합니다. j1, j2가 필요합니다.
- 리턴(P[j2] - P[j1]) /(j2 - j1)
선체 :=[-1]
인덱스 :=[0]
범위 1에서 P 크기까지의 j에 대해 수행
- 동안 선체 및 교차(indexes[-1], j) <=hull[-1], do
  - 헐에서 마지막 요소 삭제
  - 인덱스에서 마지막 요소 삭제
- 선체 끝에 교차(indexes[-1], j) 삽입
- 인덱스 끝에 j 삽입
as :=기본
각 i, 인덱스 i의 x 및 A의 항목 x에 대해 수행
- j :=정렬된 순서를 유지하면서 x가 헐에서 삽입될 수 있는 부분
- j :=j의 최대값 - 1, 0
- ans :=ans의 최대값, base + eval_at(i, x) - eval_at(indexes[j], x)
모드로 반환 (10^9 + 7)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

import bisect
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
      def eval_at(j, x):
         return -j * x + P[j]
      def intersection(j1, j2):
         return (P[j2] - P[j1]) / (j2 - j1)
      hull = [-1]
      indexes = [0]
      for j in range(1, len(P)):
         while hull and intersection(indexes[-1], j) <= hull[-1]:
            hull.pop()
            indexes.pop()
         hull.append(intersection(indexes[-1], j))
         indexes.append(j)
      ans = base
      for i, x in enumerate(A):
         j = bisect.bisect(hull, x)
         j = max(j - 1, 0)
         ans = max(ans, base + eval_at(i, x) - eval_at(indexes[j], x))
      return ans % (10 ** 9 + 7)

ob = Solution()
print (ob.solve([4, 2, 1]))

입력

[4, 2, 1]