মনে করুন nums নামে একটি অ্যারে আছে, আমাদের nums-এর প্রতিটি নন-এম্পটি সাবঅ্যারের সর্বোচ্চ মিন-প্রোডাক্ট বের করতে হবে। যেহেতু উত্তর বড় হতে পারে, মডুলো 10^9+7-এ রিটার্ন করুন। একটি অ্যারের মিন-প্রোডাক্ট হল অ্যারেতে ন্যূনতম মান গুণ অ্যারেতে সব মানের যোগফল। তাই যদি অ্যারে [4,3,6] হয় (ন্যূনতম মান ৩) তবে এর মিন-প্রোডাক্ট 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
stack := একটি নতুন স্ট্যাক
rsum := 0, res := 0
nums-এর শেষে 0 ইনসার্ট করুন
nums-এ প্রতিটি ইন্ডেক্স i এবং মান v-এর জন্য, করুন
যতক্ষণ stack খালি নয় এবং nums[stack-এর টপের ইন্ডেক্স] >= v, করুন
(index, val) := stack-এর টপ এবং এটি পপ করুন
arrSum := rsum
যদি stack খালি নয়, তবে
arrSum := rsum - stack-এর টপের ভ্যালু
res := res এবং (nums[index]*arrSum) এর মধ্যে সর্বোচ্চ
rsum := rsum + v
stack-এর শেষে (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]
আউটপুট
30
