सी ++ में सबरे न्यूनतम का योग

मान लीजिए कि हमारे पास पूर्णांक 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 है।

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

• मी :=1 x 10^9 + 7

• दो विधियों को परिभाषित करें, जोड़ें () a, b लेगा और (a mod m + b mod m) mod m लौटाएगा, mul () a, b लेगा और (a mod m * b mod m) मॉड m<लौटाएगा। /पी>

• मुख्य विधि सरणी ए लेगी, एक स्टैक सेंट को परिभाषित करेगी, और एन सेट करेगी:=सरणी ए का आकार

• आकार n के बाईं ओर दो सरणियों को परिभाषित करें और -1 से भरें, और दूसरा आकार n के दाईं ओर है, n से भरें

• उत्तर सेट करें:=0

• मैं के लिए 0 से n - 1 की सीमा में

  • जबकि सेंट खाली नहीं है और ए [स्टैक टॉप]> =ए [i], सेंट से हटाएं

  • अगर सेंट खाली नहीं है, तो बाएं सेट करें [i]:=सेंट के ऊपर

  • मुझे सेंट में डालें

• जबकि सेंट खाली नहीं है, तो सेंट हटाएं

• मैं के लिए n - 1 से 0 तक की श्रेणी में हूं

  • जबकि सेंट खाली नहीं है और ए [स्टैक टॉप]> =ए [i], सेंट से हटाएं

  • अगर सेंट खाली नहीं है, तो दाएं सेट करें [i]:=सेंट के ऊपर

  • मुझे सेंट में डालें

• मैं के लिए 0 से n - 1 की सीमा में

  • लेफ्टबाउंड:=i - लेफ्ट [i] + 1, राइटबाउंड:=राइट [i] - 1 - i

  • contri :=1 + लेफ्टबाउंड + राइटबाउंड + (लेफ्टबाउंड * राइटबाउंड)

  • उत्तर:=जोड़ें (उत्तर और मूल (विपरीत, ए [i]))

• वापसी उत्तर

उदाहरण(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