โปรแกรมหา Power สูงสุดของลิสต์หลังย้ายสมาชิกหนึ่งตัวใน Python

คำอธิบายโจทย์

Power ของลิสต์ = Σ(i+1) * A[i] สามารถย้ายสมาชิกหนึ่งตัวไปตำแหน่งไหนก็ได้ (หรือไม่ย้าย) หา Power สูงสุด mod 10^9+7

ตัวอย่าง

nums = [4, 2, 1] → เอาต์พุต: 16

วิธีแก้ปัญหา

Convex Hull Trick (CHT) / Line Container:

คำนวณ base power และ prefix sum P
ย้าย A[i] ไป j: Δ = -j*A[i] + P[j] - (-i*A[i] + P[i]) = eval_at(j) - eval_at(i)
สำหรับแต่ละ i หา j ที่ maximize eval_at(j) - eval_at(i) โดย x = A[i]
ใช้ Convex Hull ของเส้น y = -j*x + P[j] เพื่อ query max ได้ใน O(log n)

โค้ด Python

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]