Computer >> Máy Tính >  >> Lập trình >> C ++

Tổng số tối thiểu của mảng con trong C ++

Giả sử chúng ta có một mảng các số nguyên A. Chúng ta phải tìm tổng của min (B), trong đó B nằm trên mọi mảng con (liền kề) của A. Vì câu trả lời có thể rất lớn, sau đó trả về câu trả lời trong modulo 10 ^ 9 + 7. Vì vậy, nếu đầu vào là [3,1,2,4], thì đầu ra sẽ là 17, bởi vì các mảng con là [3], [1], [ 2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4] , vì vậy số tối thiểu là [3,1,2,4,1,1,2,1,1,1] và tổng là 17.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • m:=1 x 10 ^ 9 + 7

  • Xác định hai phương thức, add () sẽ nhận a, b và trả về (a mod m + b mod m) mod m, mul () sẽ nhận a, b và trả về (a mod m * b mod m) mod m

  • Phương thức main sẽ lấy mảng A, xác định một ngăn xếp và đặt n:=size của mảng A

  • Xác định hai mảng bên trái có kích thước n và tô bằng -1, và một mảng khác ở bên phải kích thước n, tô bằng n

  • đặt ans:=0

  • cho tôi trong phạm vi từ 0 đến n - 1

    • trong khi st không trống và A [stack top]> =A [i], xóa khỏi st

    • nếu st không trống, thì đặt bên trái [i]:=top of st

    • chèn tôi vào st

  • trong khi st không trống, sau đó xóa st

  • đối với tôi trong phạm vi n - 1 xuống 0

    • trong khi st không trống và A [stack top]> =A [i], xóa khỏi st

    • nếu st không trống, thì đặt bên phải [i]:=top of st

    • chèn tôi vào st

  • cho tôi trong phạm vi từ 0 đến n - 1

    • leftBound:=i - left [i] + 1, rightBound:=right [i] - 1 - i

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

    • ans:=add (ans và mul (contri, A [i]))

  • trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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));
}

Đầu vào 

[3,1,2,4]

Đầu ra 

17