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

Cho danh sách nums N số dương. Có thể chọn 1 phần tử và di chuyển (không hoán đổi) đến vị trí bất kỳ (hoặc không di chuyển). Power của danh sách = sum((i+1) * nums[i]). Tìm power lớn nhất có thể đạt được.

Ví dụ: nums = [6, 2, 3] → di chuyển 6 về cuối thành [2, 3, 6] → power = 2*1 + 3*2 + 6*3 = 26.

Giải thuật (Prefix Sum + Thử mọi vị trí di chuyển)

1. Tính base = power ban đầu, mảng prefix sum P.
2. Với mỗi phần tử x tại chỉ số i, thử di chuyển đến mọi vị trí j:
   • Delta = P[i] - P[j] - (i - j) * x.
   • Cập nhật ans = max(ans, base + delta).

Ví dụ minh họa

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))  # Output: 26

Đầu vào / Đầu ra

Input: [6, 2, 3]

Output: 26