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。

為了解決這個問題，我們將遵循以下步驟：

  • P := [0]

  • base := 0

  • 對於A中每個索引i和專案x，執行：

    • 在P的末尾插入P[-1] + x

    • base := base + i * x

  • 定義一個函式 eval_at()。這將需要 j, x

    • 返回 -j * x + P[j]

  • 定義一個函式 intersection()。這將需要 j1, j2

    • 返回 (P[j2] - P[j1]) /(j2 - j1)

  • hull := [-1]

  • indexes := [0]

  • 對於範圍從1到P大小的j，執行：

    • 當 hull 不為空且 intersection(indexes[-1], j) <= hull[-1] 時，執行：

      • 刪除hull的最後一個元素

      • 刪除indexes的最後一個元素

    • 在hull的末尾插入intersection(indexes[-1], j)

    • 在indexes的末尾插入j

  • ans := base

  • 對於A中每個索引i和專案x，執行：

    • j := x可以在hull中插入的部分，保持排序順序

    • j := max(j - 1, 0)

    • ans := max(ans, base + eval_at(i, x) - eval_at(indexes[j], x))

  • 返回 ans mod (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

更新於：2020年12月23日

173 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告