목록이 있고 목록의 힘이 모든 인덱스에 대한 (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]
출력
16