# 原题

Given an array of integers `A`, find the sum of `min(B)`, where `B` ranges over every (contiguous) subarray of `A`.

Since the answer may be large, return the answer modulo `10^9 + 7`.

Example 1:

```Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.```

Note:

1. `1 <= A.length <= 30000`
2. `1 <= A[i] <= 30000`

# 题解

## 糟糕的动态规划

### 递推关系

``````// i（从1开始计数） 指向当前元素的指针
// j（从1开始计数） 从i位置开始，向左跨越(j - 1)个元素
// d[i][j] 代表从第i个元素开始，向左跨越(j - 1)个元素的子序列中最小的值
// {2, 1, 2, 4, 2, 4}
// 举例: i = 4，j = 3, 那么dp[i][j]就是{1, 2, 4}子序列的最小值即1
// 那么有如下递推关系（状态转移方程）
dp[i][j] = A[i - 1]; // j == 1 && i == 1
dp[i][j] = min(A[i - 1], dp[i - 1][j - 1]); // j > 1 && i > 1``````

### 代码

``````/**
* https://leetcode.com/problems/sum-of-subarray-minimums/
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int mod = 1000000007;
map<int, map<int, int>> dp;
map<int, map<int, int>>::iterator it;
map<int, int>::iterator itt;
int sum = 0, c_min;
for (int i = 1; i <= (int)A.size(); i++) {
for (int j = 1; j <= i; j++) {
if (j == 1) {
map<int, int> sub_map;
c_min = A[i - 1];
sub_map.insert(make_pair(j, c_min));
dp.insert(make_pair(i, sub_map));
//dp[i][j] = A[i - 1];
} else {
it = dp.find(i - 1);
itt = (it->second).find(j - 1);
c_min = min(A[i - 1], itt->second);
it = dp.find(i);
(it->second).insert(make_pair(j, c_min));
dp.insert(make_pair(i, it->second));
//dp[i][j] = min(A[i - 1], dp[i - 1][j - 1]);
}
sum = (sum + c_min) % mod;
}
}
return sum;
}
};

int main(int argc, char * argv[]) {
int c = 0;
Solution * s = new Solution();
vector<int> l1;
l1.push_back(81);
l1.push_back(55);
l1.push_back(2);
c = s->sumSubarrayMins(l1);
cout<<c<<endl;
}``````

## 动态规划 & 单调栈

``````// {2, 1, 2, 4, 2, 4}
// dp[3] 代表的左右子序列中最小值之和，即子序列：{4} {2, 4} {1, 2, 4} {2, 1, 2, 4}
// 子列中最小值的和 即4 + 2 + 1 + 1 = 8
// 故 dp[3] = 8``````

### 递推关系

``````// d = i - j 即 j = i - d
dp[i] = A[i]; // i == 1
dp[i] = A[i] * d + dp[i - d]; // i > 1``````

``````// {2, 1, 2, 4, 2, 4}
//
// i = 0 栈（头->尾）：{[2, 1]}
// 其中2代表A[i]元素的值，1代表的是 当前元素作为最小值的情况，向左的子序列的最大长度
//
// i = 1 栈（头->尾）：{[1, 2]} 发现，[2, 1]元素没有了
// 是因为压栈时为了保持从头到尾单调递减的性质，把之前的元素pop，并将其距离自增1
//
// i = 2 栈（头->尾）：{[2,1], [1, 2]}``````

### 代码

``````/**
* https://leetcode.com/problems/sum-of-subarray-minimums/
*/
#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <cmath>

using namespace std;

class Solution {
stack<pair<int, int>> st;
public:
int next(int price) {
int d = 1;
while (!st.empty() && st.top().first >= price) {
d += st.top().second;;
st.pop();
}
st.push(make_pair(price, d));
return d;
}
int sumSubarrayMins(vector<int>& A) {
int a = 0, l = A.size(), d, mod = 1000000007;
int dp[A.size()];
for (int i = 0; i < l; i++) {
d = next(A[i]);
//dp[i] = A[i] * d + dp[i - d];
dp[i] = (A[i] * d) % mod;
if (i - d >= 0) dp[i] = (dp[i] + dp[i - d]) % mod;
a = (a + dp[i]) % mod;
}
return a;
}
};

int main(int argc, char * argv[]) {
int c = 0;
Solution * s = new Solution();
vector<int> l1;
l1.push_back(81);
l1.push_back(55);
l1.push_back(2);
c = s->sumSubarrayMins(l1);
cout<<c<<endl;
}``````

### 复杂度分析

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.