通过 86/87 测试的 Leetcode 子数组最小值之和。可能是我的模计算问题

Question

我正在解决leetcode中的子数组最小值之和问题。

问题描述- 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围遍及 arr 的每个（连续）子数组。由于答案可能很大，return答案modulo (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], [3,1,2,4].

最小值是 3、1、2、4、1、1、2、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 值。

我的Output:372485114

预期：667452382

看来我的 MOD 10^9 + 7 计算有误，但我似乎无法弄清楚问题所在。

Answer 1

我怀疑总和
sum + (((i - left + 1) * (right - i + 1)) * (arr[i]))
溢出，因为它是按 int.

完成的

将其更改为 long（例如，使用 ... + 1L... 或在乘法之前进行转换），并在转换回 int（或使用 long sum）之前进行取模。

最终，根据输入数字的范围，在添加之前还要计算(((i - left + 1) * (right - i + 1)) * (arr[i]))的模数。

通过 86/87 测试的 Leetcode 子数组最小值之和。可能是我的模计算问题

Leetcode Sum of Subarray Minimums passing 86/87 tests. Probably an Issue with my modulo calculation

java

modulo