C++ में सबएरे मिनिमम का योग

मान लीजिए हमारे पास इंटीजर्स का एक ऐरे A है। हमें min(B) का योग ढूंढना है, जहां B, A के हर (सन्निहित) सबएरे पर रेंज करता है। चूंकि उत्तर बहुत बड़ा हो सकता है, इसलिए उत्तर को मॉड्यूलो 10^9 + 7 में लौटाएं। यदि इनपुट [3,1,2,4] है, तो आउटपुट 17 होगा, क्योंकि सबएरे हैं [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], और योग 17 है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• 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 का आकार सेट करें
• -1 से भरे आकार n के दो ऐरे लेफ्ट परिभाषित करें, और दूसरा आकार n का राइट है, n से भरें
• ans := 0 सेट करें
• i के लिए 0 से n - 1 तक की रेंज में
  • जब तक st खाली नहीं है और A[स्टैक टॉप] >= A[i], st से डिलीट करें
  • यदि st खाली नहीं है, तो लेफ्ट[i] := st का टॉप सेट करें
  • i को st में डालें
• जब तक st खाली नहीं है, तब तक st डिलीट करें
• i के लिए n - 1 से 0 तक डाउन टू की रेंज में
  • जब तक st खाली नहीं है और A[स्टैक टॉप] > A[i], st से डिलीट करें
  • यदि st खाली नहीं है, तो राइट[i] := st का टॉप सेट करें
  • i को st में डालें
• i के लिए 0 से n - 1 तक की रेंज में
  • लेफ्टबाउंड := i - लेफ्ट[i] + 1, राइटबाउंड := राइट[i] - 1 - i
  • कॉन्ट्री := 1 + लेफ्टबाउंड + राइटबाउंड + (लेफ्टबाउंड * राइटबाउंड)
  • ans := add(ans और mul(कॉन्ट्री, 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]

आउटपुट

17