Chương trình nhận giá trị sức mạnh tối đa của danh sách bằng cách sắp xếp lại các phần tử trong Python

Giả sử chúng ta có một danh sách gồm N số dương. Bây giờ chúng ta có thể chọn bất kỳ giá trị đơn lẻ nào từ danh sách và di chuyển (không hoán đổi) nó đến bất kỳ vị trí nào. Chúng tôi cũng không thể di chuyển bất kỳ vị trí nào. Vì vậy, chúng ta phải tìm sức mạnh cuối cùng tối đa có thể có của danh sách là bao nhiêu? Như chúng ta biết sức mạnh của một danh sách là tổng của (index + 1) * value_at_index trên tất cả các chỉ số i.

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

Vì vậy, nếu đầu vào là nums =[6, 2, 3], thì đầu ra sẽ là 26, vì chúng ta có thể di chuyển 6 đến cuối để có được danh sách [2, 3, 6] vì vậy lũy thừa là:(2 * 1) + (3 * 2) + (6 * 3) =26.

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

• P:=một danh sách có giá trị 0

• cơ sở:=0

• đối với mỗi chỉ số i và giá trị x của A, thực hiện

  • chèn phần tử cuối cùng của P + x vào cuối P

  • cơ sở:=base + (i + 1) * x

• ans:=base

• đối với mỗi chỉ số i và giá trị x trong A, thực hiện

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

    • ans:=tối đa ans và (base + P [i] - P [j] - (i - j) * x)

• trả lại ans

Ví dụ

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

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

Đầu vào

[6, 2, 3]

Đầu ra

26