C++의 하위 배열 최소값 합계

정수 A의 배열이 있다고 가정합니다. min(B)의 합을 찾아야 합니다. 여기서 B는 A의 모든 (인접) 하위 배열에 걸쳐 있습니다. 대답은 매우 큰 경우, 모듈로 10^9 + 7로 답을 반환합니다. 따라서 입력이 [3,1,2,4]와 같으면 하위 배열이 [3], [1], [이기 때문에 출력은 17이 됩니다. 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가 비어 있지 않으면 left[i] :=top of st
  로 설정합니다.
- i를 st에 삽입
st가 비어 있지 않은 동안 st를 삭제합니다.
범위 n – 1에서 0까지의 i에 대해
- st가 비어 있지 않고 A[stack top]>=A[i]인 동안 st에서 삭제
- st가 비어 있지 않으면 right[i] :=top of st
  로 설정합니다.
- i를 st에 삽입
0 ~ n – 1 범위의 i에 대해
- leftBound :=i – left[i] + 1, rightBound :=right[i] – 1 – i
- contri :=1 + leftBound + rightBound + (leftBound * rightBound)
- ans :=add(ans 및 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]