পাইথনে একটি তালিকার সর্বোচ্চ চূড়ান্ত শক্তি খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের একটি তালিকা আছে এবং একটি তালিকার শক্তি (সূচক + 1) * value_at_index এর সমষ্টি দ্বারা সংজ্ঞায়িত করা হয়েছে সমস্ত সূচকে। বিকল্পভাবে, আমরা এটিকে এভাবে উপস্থাপন করতে পারি −

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

এখন, আমাদের কাছে একটি তালিকার সংখ্যা রয়েছে যাতে N ধনাত্মক পূর্ণসংখ্যা রয়েছে। আমরা তালিকার যেকোনো একবচন মান নির্বাচন করতে পারি, এবং এটিকে যেকোনো অবস্থানে সরাতে (অদলবদল নয়), এটি তালিকার শুরুতে বা শেষ পর্যন্ত স্থানান্তরিত করা যেতে পারে। আমরা কোনো অবস্থান সরানো না করা বেছে নিতে পারি। আমাদের তালিকার সর্বোচ্চ সম্ভাব্য চূড়ান্ত শক্তি খুঁজে বের করতে হবে। ফলাফলটি 10^9 + 7 দ্বারা পরিবর্তন করতে হবে।

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[৪, ২, ১], তাহলে আউটপুট হবে ১৬।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

P :=[0]
ভিত্তি :=0
প্রতিটি i, সূচী i তে x এবং A, 1, do
এ আইটেম x এর জন্য
- P
  এর শেষে P[-1] + x ঢোকান
- base :=base + i * x
একটি ফাংশন সংজ্ঞায়িত করুন eval_at()। এটি j, x
লাগবে
- রিটার্ন -j * x + P[j>
একটি ফাংশন intersection() সংজ্ঞায়িত করুন। এটি j1, j2
লাগবে৷
- রিটার্ন(P[j2] - P[j1]) /(j2 - j1)
hull :=[-1]
ইনডেক্স :=[0]
j এর জন্য রেঞ্জ 1 থেকে P এর আকার, করুন
- hull এবং intersection(indexes[-1], j) <=hull[-1], do
  - হুল থেকে শেষ উপাদান মুছুন
  - সূচী থেকে শেষ উপাদান মুছুন
- হুলের শেষে ছেদ (সূচিপত্র[-1], j) সন্নিবেশ করুন
- ইনডেক্সের শেষে j ঢোকান
উত্তর :=ভিত্তি
প্রতিটি i এর জন্য, সূচী i তে x এবং A এ আইটেম x, করুন
- 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]