Chương trình tìm công suất cuối cùng tối đa của một danh sách trong Python

Công suất của danh sách: sum((i+1) * list[i]) với i từ 0 đến n-1. Cho danh sách nums N số nguyên dương. Có thể chọn một phần tử và di chuyển (không hoán đổi) đến bất kỳ vị trí nào (đầu, cuối, hoặc giữa). Tìm công suất tối đa có thể đạt được. Kết quả modulo 10^9+7.

Ví dụ: nums = [4, 2, 1] → 16.

Giải pháp

Sử dụng Convex Hull Trick (CHT) để tối ưu hóa việc chọn vị trí di chuyển:

• P: prefix sum của nums (1-indexed)
• base: công suất ban đầu
• eval_at(j, x) = -j*x + P[j]: giá trị nếu chèn x tại vị trí j
• intersection(j1, j2): giao điểm của hai đường thẳng
• Xây dựng upper hull của các đường thẳng eval_at(j, x)
• Với mỗi phần tử x tại vị trí i, tìm j tối ưu trên hull bằng binary search
• ans = max(base, base + eval_at(i, x) - eval_at(indexes[j], x))

Ví dụ minh họa

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