1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
// 907. Sum of Subarray Minimums
#include <stdio.h>
#include <stdlib.h>
/*
* given an array of integers 'arr', find the sum of 'min(b)', where 'b' ranges
* over every contiguous subarray of 'arr'. since the answer may be large,
* return the answer modulo 10^9+7
*/
int sumSubarrayMins(int *arr, int arr_size) {
int *stk = calloc(arr_size, sizeof(int));
int *ple = calloc(arr_size, sizeof(int));
int *nle = calloc(arr_size, sizeof(int));
int pt = -1;
for (int i = 0; i < arr_size; i++) {
ple[i] = i + 1;
nle[i] = arr_size - i;
}
for (int i = 0; i < arr_size; i++) {
while (pt != -1 && arr[stk[pt]] > arr[i]) {
int x = stk[pt];
nle[x] = i - x;
pt--;
}
ple[i] = (pt == -1 ? i + 1 : i - stk[pt]);
stk[++pt] = i;
}
free(stk);
int sum = 0, mod = 1e9 + 7;
for (int i = 0; i < arr_size; i++)
sum = (sum + arr[i] * (unsigned)ple[i] * (unsigned)nle[i]) % mod;
free(ple), free(nle);
return sum;
}
int main() {
int a1[] = {3, 1, 2, 4}, a2[] = {11, 81, 94, 43, 3};
printf("%d\n", sumSubarrayMins(a1, 4)); // expect: 17
printf("%d\n", sumSubarrayMins(a2, 5)); // expect: 444
}
|