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<রিটার্ন করবে। /P>

• প্রধান পদ্ধতিটি অ্যারে A নেবে, একটি স্ট্যাক st সংজ্ঞায়িত করবে এবং n :=অ্যারের আকার A

  সেট করবে।

• n আকারের বামে দুটি অ্যারে সংজ্ঞায়িত করুন এবং -1 দিয়ে পূরণ করুন, এবং অন্যটি n আকারের ডানদিকে, n দিয়ে পূরণ করুন

• সেট উত্তর :=0

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • যখন st খালি নয় এবং A[stack top]>=A[i], st

    থেকে মুছে দিন

  • যদি st খালি না হয়, তাহলে লেফট[i] সেট করুন :=st এর উপরের

  • আমাকে st

    -এ ঢোকান

• যখন st খালি নেই, তারপর st মুছুন

• i রেঞ্জ n – 1 থেকে 0

  পর্যন্ত

  • যখন st খালি নয় এবং A[stack top]>=A[i], st

    থেকে মুছে দিন

  • যদি st খালি না হয়, তাহলে ডান [i] :=st এর শীর্ষ

    সেট করুন

  • আমাকে st

    -এ ঢোকান

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • বামবাউন্ড :=i – বাম[i] + 1, রাইটবাউন্ড :=ডান[i] – 1 – i

  • contri :=1 + leftBound + rightBound + (leftBound * rightBound)

  • ans :=add(ans and mul(contri, A[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