在Python中找到列表的最大最终功率的程序

假设我们有一个列表，列表的功率定义为所有索引上的（索引+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。

要解决此问题，我们将遵循以下步骤-

P：= [0]
基数：= 0
对于索引i和项x中的每个i，x在A中，执行以下操作1-
- 在P的末尾插入P[-1] + x
- 基数：=基数+ i * x
定义一个函数eval_at()。这将采用j，x
- 返回-j * x + P [j]
定义一个函数intersection()。这将采用j1，j2
- return(P[j2] – P[j1]) /（j2-j1）
hull：= [-1]
索引：= [0]
对于P的范围内的每个j，执行以下操作1
- 同时hull和intersection（indexes [-1]，j）<= hull [-1]时
  - 从hull中删除最后一个元素
  - 从索引中删除最后一个元素
- 在hull的末尾插入intersection（indexes [-1]，j）
- 在indexes的末尾插入j
ans：=基数
对于在A中的索引i和项x，执行以下操作-
- j：= x可以插入的部分hull，保持排序顺序
- j：= j-1的最大值，0
- ans：= ans，base + eval_at（i，x）-eval_at（indexes [j]，x）的最大值
返回ans mod（10 ** 9 + 7）

更多Python相关文章，请阅读：Python 教程

示例

让我们看一下以下实现，以更好地理解-

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]))