C++-এ সাবঅ্যারে মিনিমামগুলোর যোগফল

মনে করুন একটি পূর্ণসংখ্যার অ্যারে `A` আছে। আমাদের `min(B)`-এর যোগফল বের করতে হবে, যেখানে `B` হলো `A`-এর প্রতিটি (কন্টিগুয়াস) সাবঅ্যারে। যেহেতু উত্তর খুব বড় হতে পারে, তাই উত্তরটি মডুলো 10^9 + 7-এ রিটার্ন করতে হবে। যদি ইনপুট `[3,1,2,4]` হয়, তবে আউটপুট হবে ১৭, কারণ সাবঅ্যারেগুলো হলো [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], তাই মিনিমামগুলো হলো [3,1,2,4,1,1,2,1,1,1], এবং যোগফল ১৭।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

`m := 1 x 10^9 + 7`
দুটি মেথড সংজ্ঞায়িত করুন, `add()` `a`, `b` নেবে এবং `(a mod m + b mod m) mod m` রিটার্ন করবে, `mul()` `a`, `b` নেবে এবং `(a mod m * b mod m) mod m` রিটার্ন করবে
মেইন মেথড অ্যারে `A` নেবে, একটি স্ট্যাক `st` সংজ্ঞায়িত করুন, এবং `n := A`-এর আকার সেট করুন
`left` নামক একটি অ্যারে আকার `n` এবং -1 দিয়ে ফিল করুন, আরেকটি `right` আকার `n` এবং `n` দিয়ে ফিল করুন
`ans := 0` সেট করুন
`i` = 0 থেকে `n-1` পর্যন্ত
- যখন `st` খালি না থাকে এবং `A[st.top()] >= A[i]`, `st`-থেকে ডিলিট করুন
- যদি `st` খালি না থাকে, তবে `left[i] := st.top()` সেট করুন
- `i`-কে `st`-এ ইনসার্ট করুন
যখন `st` খালি না থাকে, `st` ডিলিট করুন
`i` = `n-1` থেকে 0 পর্যন্ত
- যখন `st` খালি না থাকে এবং `A[st.top()] > A[i]`, `st`-থেকে ডিলিট করুন
- যদি `st` খালি না থাকে, তবে `right[i] := st.top()` সেট করুন
- `i`-কে `st`-এ ইনসার্ট করুন
`i` = 0 থেকে `n-1` পর্যন্ত
- `leftBound := i - left[i] + 1`, `rightBound := right[i] - 1 - i`
- `contri := 1 + leftBound + rightBound + (leftBound * rightBound)`
- `ans := add(ans, mul(contri, A[i]))`
`ans` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli MOD = 1e9 + 7; class Solution { public:    lli add(lli a, lli b){       return (a % MOD + b % MOD) % MOD;    }    lli mul(lli a, lli b){       return (a % MOD * b % MOD) % MOD;    }    int sumSubarrayMins(vector<int>& A) {       stack <int> st;       int n = A.size();       vector <int> left(n, -1);       vector <int> right(n, n);       int ans = 0;       for(int i = 0; i < n; i++){          while(!st.empty() && A[st.top()] >= A[i]){          st.pop();       }       if(!st.empty())left[i] = st.top();          st.push(i);       }       while(!st.empty())st.pop();       for(int i = n - 1; i >= 0; i--){          while(!st.empty() && A[st.top()] > A[i]){             st.pop();          }          if(!st.empty())right[i] = st.top();             st.push(i);       }       for(int i = 0; i < n; i++){          int leftBound = i - (left[i] + 1);          int rightBound = (right[i] - 1) - i;          int contri = 1 + leftBound + rightBound + (leftBound * rightBound);          ans = add(ans, mul(contri, A[i]));       }       return ans;    } }; main(){    vector<int> v = {3,1,2,4};    Solution ob;    cout << (ob.sumSubarrayMins(v)); }

ইনপুট

[3,1,2,4]