पायथन में सूची की अधिकतम अंतिम शक्ति ज्ञात करने का प्रोग्राम

मान लीजिए, हमारे पास एक सूची है और एक सूची की शक्ति को सभी इंडेक्स पर (इंडेक्स + 1) * इंडेक्स_पर_मान के योग के रूप में परिभाषित किया गया है। वैकल्पिक रूप से, हम इसे इस तरह दर्शा सकते हैं:

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

अब, हमारे पास nums नामक एक सूची है जिसमें N धनात्मक पूर्णांक हैं। हम सूची में किसी एक मान का चयन कर सकते हैं, और उसे किसी भी स्थिति में ले जा सकते हैं (स्वैप नहीं), इसे सूची की शुरुआत में या अंत में स्थानांतरित किया जा सकता है। हम किसी भी स्थिति को न ले जाने का विकल्प भी चुन सकते हैं। हमें सूची की अधिकतम संभव अंतिम शक्ति ज्ञात करनी है। परिणाम को 10^9 + 7 से मोड करना होगा।

इसलिए, यदि इनपुट nums = [4, 2, 1] जैसा है, तो आउटपुट 16 होगा।

हल करने के चरण

P := [0]
base := 0
प्रत्येक i, x के लिए इंडेक्स i और आइटम x में A, 1 से, करें
- P[-1] + x को P के अंत में डालें
- base := base + i * x
eval_at() फ़ंक्शन परिभाषित करें। यह j, x लेगा
- -j * x + P[j] लौटाएं
intersection() फ़ंक्शन परिभाषित करें। यह j1, j2 लेगा
- (P[j2] - P[j1]) / (j2 - j1) लौटाएं
hull := [-1]
indexes := [0]
j के लिए 1 से P के आकार तक की रेंज में, करें
- जब तक hull और intersection(indexes[-1], j) <= hull[-1], करें
  - hull से अंतिम तत्व हटाएं
  - indexes से अंतिम तत्व हटाएं
- intersection(indexes[-1], j) को hull के अंत में डालें
- j को indexes के अंत में डालें
ans := base
प्रत्येक i, x के लिए इंडेक्स i और आइटम x में A, करें
- j := वह भाग जहां x को hull में डाला जा सकता है, क्रम बनाए रखते हुए
- j := j - 1 और 0 का अधिकतम
- ans := ans, base + eval_at(i, x) - eval_at(indexes[j], x) का अधिकतम
ans mod (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]