পাইথনে একটি লিস্টের সব সাবলিস্টের মিনিমামের যোগফল বের করার প্রোগ্রাম

পাইথনে একটি নাম্বার লিস্ট nums দেওয়া আছে। লিস্টের সব সম্ভাব্য সাবলিস্ট (subarray) এর মিনিমাম ভ্যালুগুলোর যোগফল বের করতে হবে। ফলাফল বড় হলে 10^9 + 7 দিয়ে মডুলো নেওয়া হবে।

উদাহরণ

ইনপুট: nums = [5, 10, 20, 10, 0]

আউটপুট: 90

ব্যাখ্যা: সব সাবলিস্ট এবং তাদের মিনিমাম:

• দৈর্ঘ্য ১: [5],[10],[20],[10],[0] -> মিন: 5,10,20,10,0
• দৈর্ঘ্য ২: [5,10],[10,20],[20,10],[10,0] -> মিন: 5,10,10,0
• দৈর্ঘ্য ৩: [5,10,20],[10,20,10],[20,10,0] -> মিন: 5,10,0
• দৈর্ঘ্য ৪: [5,10,20,10],[10,20,10,0] -> মিন: 5,0
• দৈর্ঘ্য ৫: [5,10,20,10,0] -> মিন: 0
• যোগফল: 5+10+20+10+0+5+10+10+0+5+10+0+5+0+0 = 90

এলগরিদম (Monotonic Stack + Prefix Sum)

এটি একটি ক্লাসিক "Sum of Subarray Minimums" সমস্যা (LeetCode 907)। প্রতিটি এলিমেন্ট কতগুলো সাবলিস্টে মিনিমাম হবে তা গণনা করা হয়।

1. ans = 0, s = [] (স্ট্যাক: [index, value, contribution]), temp_sum = 0
2. প্রতিটি (index, value) in enumerate(nums) এর জন্য:
   • যখন s খালি নয় এবং value <= s[-1][1]:
     • temp_sum -= s[-1][2] (পুরানো কন্ট্রিবিউশন বাদ দিন)
     • s.pop()
   • যদি s খালি: s.append([index, value, (index+1)*value])
   • অন্যথায়: s.append([index, value, (index - s[-1][0])*value])
   • temp_sum += s[-1][2]
   • ans += temp_sum
3. ans % (10**9 + 7) রিটার্ন করুন

পাইথন ইমপ্লিমেন্টেশন

def solve(nums):
    ans = 0
    s = []
    temp_sum = 0
    for index, value in enumerate(nums):
        while s and value <= s[-1][1]:
            temp_sum -= s[-1][2]
            s.pop()
        if not s:
            s.append([index, value, (index + 1) * value])
        else:
            s.append([index, value, (index - s[-1][0]) * value])
        temp_sum += s[-1][2]
        ans += temp_sum
    return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))  # Output: 90

ইনপুট

[5, 10, 20, 10, 0]

আউটপুট

90

ব্যাখ্যা

• স্ট্যাক (s): মনোটনিক ইনক্রিজিং স্ট্যাক (মান অনুযায়ী)। প্রতিটি এন্ট্রি: [ইন্ডেক্স, মান, কন্ট্রিবিউশন]।
• কন্ট্রিবিউশন: করেন্ট এলিমেন্ট নতুন সাবলিস্টগুলোর মিনিমাম হিসেবে কতটুকু যোগ করবে।
• temp_sum: বর্তমান ইন্ডেক্স পর্যন্ত সমস্ত সাবলিস্টের মিনিমামের যোগফল (এন্ডিং অ্যাট করেন্ট ইন্ডেক্স)।
• যখন ছোট বা সমান মান আসে, বড় মানগুলো স্ট্যাক থেকে বের করা হয় (তাদের কন্ট্রিবিউশন শেষ)।

সময় জটিলতা

O(n) — প্রতিটি এলিমেন্ট স্ট্যাকে একবার পুশ এবং একবার পপ হয়। স্পেস: O(n)।

এই অ্যালগরিদম বড় ইনপুট (১০⁵+) এর জন্যও খুব দ্রুত কাজ করে।