在Python中查找列表的最大最终幂的程序
假设我们有一个列表，列表的功效由所有索引上的（index+1）*value_at_index的总和定义。或者，我们可以这样表示它-
$$\displaystyle\sum\limits_{i=0}^{n-1}(i+1)\timeslist[i]$$
现在，我们有一个具有N个正整数的列表nums。我们可以选择列表中的任何奇异值，然后将其移动（而不是交换）到任意位置，可以将其移动到列表的开头或结尾。我们还可以选择完全不移动任何位置。我们必须找到列表的最大可能最终功效。结果必须修改为10^9+7。
因此，如果输入类似于nums=[4，2，1]，则输出将为16。
在线示例
让我们看下面的实现以更好地理解-
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