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

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

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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पी:=[0]

• आधार :=0

• प्रत्येक के लिए मैं, सूचकांक में एक्स और ए, 1 में आइटम एक्स, करो

  • P[-1] + x को P के अंत में डालें

  • आधार:=आधार + मैं * x

• एक फ़ंक्शन परिभाषित करें eval_at() । इसमें j, x लगेगा

  • रिटर्न -जे * एक्स + पी [जे]

• एक फ़ंक्शन चौराहे () को परिभाषित करें। इसमें j1, j2 लगेगा

  • वापसी (पी [जे 2] - पी [जे 1]) / (जे 2 - जे 1)

• पतवार :=[-1]

• अनुक्रमणिका :=[0]

• j के लिए 1 से लेकर P के आकार तक, करें

  • हल और चौराहे के दौरान (इंडेक्स [-1], जे) <=पतवार [-1], करते हैं

    • पतवार से अंतिम तत्व हटाएं

    • अनुक्रमणिका से अंतिम तत्व हटाएं

  • हल के अंत में चौराहा (इंडेक्स [-1], जे) डालें

  • अनुक्रमणिका के अंत में j डालें

• उत्तर:=आधार

• प्रत्येक के लिए मैं, सूचकांक में एक्स और ए में आइटम एक्स, करो

  • j :=वह भाग जहाँ x को हल में डाला जा सकता है, क्रमबद्ध क्रम को बनाए रखते हुए

  • j :=अधिकतम j-1, 0

  • उत्तर:=अधिकतम उत्तर, आधार + eval_at(i, x) - eval_at(indexes[j], x)

• वापसी उत्तर मोड (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]

आउटपुट

16