পাইথনে লিস্টের সর্বোচ্চ ফাইনাল পাওয়ার বের করা (একটি এলিমেন্ট সরিয়ে)

এক লিস্টের পাওয়ার সংজ্ঞায়িত: $\sum_{i=0}^{n-1} (i+1) \times list[i]$। আমরা লিস্ট nums-এ থেকে যেকোনো একটি মান বেছে নিতে পারি এবং যেকোনো পজিশনে সরিয়ে দিতে পারি (শুরু বা শেষে)। একটি এলিমেন্ট সরিয়ে সর্বোচ্চ পাওয়ার বের করতে হবে। ফলাফল 10^9+7 দিয়ে মডুলো।

উদাহরণ: nums = [4, 2, 1] → আউটপুট 16।

সমাধানের ধাপসমূহ (Convex Hull Trick / Monotonic Queue)

P := প্রিফিক্স সাম অ্যারে (P[0]=0)। base := বর্তমান পাওয়ার।
eval_at(j, x) = -j*x + P[j] এবং intersection(j1, j2) = (P[j2]-P[j1])/(j2-j1) ফাংশন ডিফাইন করুন।
মনোটোনিক কনভেক্স হাল (Hull) বানান: hull (ইন্টারসেকশন ভ্যালু) এবং indexes (পজিশন)।
প্রতিটি i, x ∈ nums এর জন্য বাইনারি সার্চ (bisect) দিয়ে হালে সেরা পজিশন খুঁজুন এবং পাওয়ার ম্যাক্সিমাইজ করুন।
ans % (10^9+7) রিটার্ন করুন।

পাইথন কোড উদাহরণ

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]