Pythonでリストの最大の最終的な力を見つけるためのプログラム

リストがあり、リストの累乗がすべてのインデックスの（index + 1）*value_at_indexの合計によって定義されているとします。または、次のように表すこともできます-

$$ \ displaystyle \ sum \ Limits_ {i =0} ^ {n-1}（i + 1）\ times list [i] $$

これで、N個の正の整数を持つリストnumができました。リスト内の任意の特異値を選択し、それを任意の位置に移動（スワップではなく）したり、リストの最初または最後に移動したりできます。ポジションをまったく動かさないことも選択できます。リストの可能な限り最大の最終的な力を見つけなければなりません。結果は10^9+7で変更する必要があります。

したがって、入力がnums =[4、2、1]の場合、出力は16になります。

これを解決するには、次の手順に従います-

• P：=[0]

• ベース：=0

• インデックスiの各i、xおよびA、1のアイテムxについて、実行します

  • P

    の最後にP[-1]+xを挿入します

  • base：=base + i * x

• 関数eval_at（）を定義します。これにはj、xが必要です

  • -j * x + P [j]

    を返します

• 関数intersection（）を定義します。これにはj1、j2が必要です

  • return（P [j2]-P [j1]）/（j2-j1）

• 船体：=[-1]

• インデックス：=[0]

• 1からPのサイズまでの範囲のjについては、次のようにします

  • ハルと交差点（インデックス[-1]、j）<=ハル[-1]、実行

    • 船体から最後の要素を削除する

    • インデックスから最後の要素を削除する

  • 船体の最後にintersection（indexes [-1]、j）を挿入します

  • インデックスの最後にjを挿入します

• ans：=base

• インデックスiの各i、xおよびAのアイテムxについて、実行します

  • j：=ソートされた順序を維持しながら、xを船体に挿入できる部分

  • j：=最大j-1、0

  • ans：=ansの最大値、ベース+ 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