Python 列表元素重排获取最大功率值程序

假设我们有一个包含 N 个正数的列表 nums。现在我们可以从列表中选择任何单个值，并将其移动（而不是交换）到任何位置。我们也可以不将任何值移动到任何位置。所以我们必须找到列表可能的最大最终功率值是多少？众所周知，列表的功率是所有索引 i 上 (index + 1) * value_at_index 的总和。

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

因此，如果输入类似于 nums = [6, 2, 3]，则输出将为 26，因为我们可以将 6 移动到末尾以获得列表 [2, 3, 6]，因此功率为：(2 * 1) + (3 * 2) + (6 * 3) = 26。

为了解决这个问题，我们将遵循以下步骤 -

  • P := 一个值为 0 的列表

  • base := 0

  • 对于 A 的每个索引 i 和值 x，执行

    • 将 P 的最后一个元素 + x 插入到 P 的末尾

    • base := base + (i+1) * x

  • ans := base

  • 对于 A 的每个索引 i 和值 x，执行

    • 对于 j 从 0 到 A 的大小 + 1，执行

      • ans := ans 和 (base + P[i] - P[j] -(i - j) * x) 的最大值

  • 返回 ans

示例

让我们看看下面的实现以更好地理解 -

在线演示

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
      ans = base
      for i, x in enumerate(A):
         for j in range(len(A) + 1):
            ans = max(ans, base + P[i] - P[j] - (i - j) * x)
      return ans
ob = Solution()
nums = [6, 2, 3]
print(ob.solve(nums))

输入

[6, 2, 3]

输出

26

更新于: 2020-12-22

611 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告