পাইথনে সর্বাধিক সাব্যারে মিন-প্রোডাক্ট খোঁজার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে সংখ্যা আছে, আমাদের সংখ্যার প্রতিটি অ-খালি সাবয়ারের সর্বোচ্চ ন্যূনতম-উপাদান খুঁজে বের করতে হবে। যেহেতু উত্তরটি যথেষ্ট বড় হতে পারে, তাই এটিকে মডিউল 10^9+7 এ ফেরত দিন। অ্যারের ন্যূনতম-উপাদানটি অ্যারের যোগফল দ্বারা গুণিত অ্যারের সর্বনিম্ন মানের সমান। সুতরাং যদি আমাদের একটি অ্যারে থাকে [4,3,6] এর মত (সর্বনিম্ন মান 3) একটি ন্যূনতম-পণ্য 3*(4+3+6) =3*13 =39।

সুতরাং, ইনপুট যদি nums =[2,3,4,3] এর মত হয়, তাহলে আউটপুট হবে 30 কারণ আমরা ফলাফল সর্বাধিক করার জন্য সাবয়ারে [3,4,3] পেতে পারি, তাই 3*(3+4+) 3) =3*10 =30।

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

m :=10^9+7
স্ট্যাক :=একটি নতুন স্ট্যাক
rsum :=0, res :=0
সংখ্যার শেষে 0 ঢোকান
প্রতিটি সূচক i এবং মান v সংখ্যার জন্য, করুন
- যখন স্ট্যাক খালি না থাকে এবং সংখ্যা[স্ট্যাকের শীর্ষের সূচক]>=v, do
  - index, val) :=স্ট্যাকের শীর্ষ এবং স্ট্যাক থেকে এটি পপ করুন
  - arrSum:=rsum
  - যদি স্ট্যাক খালি না হয়, তাহলে
    - arrSum:=rsum - স্ট্যাকের শীর্ষের মান
  - res:=res এর সর্বোচ্চ এবং (nums[index]*arrSum)
- rsum :=rsum + v
- স্ট্যাকের শেষে পুশ (i, rsum)
রিটার্ন res mod m

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(nums):
   m = int(1e9+7)
   stack = []
   rsum = 0
   res = 0

   nums.append(0)

   for i, v in enumerate(nums):
      while stack and nums[stack[-1][0]] >= v:
         index, _ = stack.pop()

         arrSum=rsum

         if stack:
            arrSum=rsum-stack[-1][1]

         res=max(res, nums[index]*arrSum)

      rsum += v
      stack.append((i, rsum))

   return res % m

nums = [2,3,4,3]
print(solve(nums))

ইনপুট

[2,3,4,3]