ผลรวมของ Subarray ขั้นต่ำใน 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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=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

• กำหนดอาร์เรย์สองอาร์เรย์ด้านซ้ายของขนาด n และเติมด้วย -1 และอีกอาร์เรย์หนึ่งอยู่ทางด้านขวาของขนาด n เติมด้วย n

• ตั้งค่าเป็น :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ในขณะที่ st ไม่ว่างเปล่าและ A[stack top]>=A[i] ให้ลบออกจาก st

  • ถ้า st ไม่ว่าง ให้ตั้งค่า left[i] :=ด้านบนของ st

  • ใส่ i ลงใน st

• ในขณะที่ st ไม่ว่าง ให้ลบ st

• สำหรับฉันอยู่ในช่วง n – 1 ลงไปที่ 0

  • ในขณะที่ st ไม่ว่างเปล่าและ A[stack top]>=A[i] ให้ลบออกจาก st

  • ถ้า st ไม่ว่าง ให้ตั้งค่า right[i] :=ด้านบนของ st

  • ใส่ i ลงใน st

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • leftBound :=i – left[i] + 1, rightBound :=right[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