我正在解决leetcode中的子阵列最小值之和问题。
问题描述-给定一个整数数组arr，求min(b(的和，其中b在arr的每个(连续的(子数组上。由于答案可能很大，所以返回模(10^9(+7的答案。
问题示例-
输入：arr=[3,1,2,4]
输出：17
说明：
子阵列为[3]、[1]、[2]、[4]、[3，1]、[1，2]、[2，4]、[3、1,2]、[1，2，4]、[1，2,4]、[3。
最小值为3,1,2,4,1,2,1,1,1,1。总和是17。
我的解决方案-
class Solution {
int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {
int sum = 0;
for(int i=0; i<arr.length; i++) {
int left = i;
int right = i;
while(left > 0 && arr[i] <= arr[left - 1]) {
left--;
}
while(right < arr.length - 1 && arr[i] < arr[right + 1]){
right++;
}
sum = sum + (((i - left + 1) * (right - i + 1)) * (arr[i]));
sum%=MOD;
}
return sum;
}
}
我的解决方案适用于所有的测试用例，但最后一个测试用例的输入数组很大，总和值将超过mod值。
我的输出：372485114
预期：667452382
我似乎在MOD 10^9+7的计算中犯了一个错误，但我似乎无法解决这个问题。
我怀疑总和sum + (((i - left + 1) * (right - i + 1)) * (arr[i]))
溢出，因为它是作为int完成的。
将其更改为long(例如，使用... + 1L...或在相乘前进行强制转换(，并在强制转换回int之前进行模运算(或使用long sum(。
最后，根据输入数字的范围，在相加之前还计算出(((i - left + 1) * (right - i + 1)) * (arr[i]))的模块。