在Python中查找列表的最大最终幂的程序

假设我们有一个列表，列表的功效由所有索引上的（index +1）* value_at_index的总和定义。或者，我们可以这样表示它-

$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[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