Chương trình tìm ra sức mạnh cuối cùng tối đa của một danh sách bằng Python

Giả sử, chúng ta có một danh sách và sức mạnh của một danh sách được xác định bằng tổng của (index + 1) * value_at_index trên tất cả các chỉ số. Ngoài ra, chúng ta có thể trình bày nó như thế này -

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

Bây giờ, chúng ta có một danh sách nums có N số nguyên dương. Chúng ta có thể chọn bất kỳ giá trị đơn lẻ nào trong danh sách và di chuyển (không hoán đổi) giá trị đó đến bất kỳ vị trí nào, nó có thể được chuyển đến đầu danh sách hoặc đến cuối danh sách. Chúng tôi cũng có thể chọn không di chuyển bất kỳ vị trí nào. Chúng tôi phải tìm ra sức mạnh cuối cùng tối đa có thể có của danh sách. Kết quả phải được sửa đổi bởi 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là nums =[4, 2, 1], thì đầu ra sẽ là 16.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• P:=[0]

• cơ sở:=0

• đối với mỗi i, x trong chỉ mục i và mục x trong A, 1, thực hiện

  • chèn P [-1] + x vào cuối P

  • base:=base + i * x

• Định nghĩa một hàm eval_at (). Điều này sẽ mất j, x

  • return -j * x + P [j]

• Xác định một giao của hàm (). Điều này sẽ mất j1, j2

  • return (P [j2] - P [j1]) / (j2 - j1)

• thân tàu:=[-1]

• chỉ mục:=[0]

• đối với j trong phạm vi 1 đến kích thước của P, thực hiện

  • trong khi thân tàu và giao lộ (chỉ mục [-1], j) <=hull [-1], thực hiện

    • xóa phần tử cuối cùng khỏi thân tàu

    • xóa phần tử cuối cùng khỏi chỉ mục

  • chèn giao lộ (chỉ số [-1], j) vào cuối thân tàu

  • chèn j vào cuối chỉ mục

• ans:=base

• đối với mỗi mục i, x trong chỉ mục i và mục x trong A, thực hiện

  • j:=phần mà x có thể được chèn vào thân tàu, duy trì thứ tự đã sắp xếp

  • j:=tối đa của j - 1, 0

  • ans:=tối đa ans, base + eval_at (i, x) - eval_at (indexes [j], x)

• return ans mod (10 ^ 9 + 7)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[4, 2, 1]

Đầu ra

16