注册登录

求和连续子数组最小值

题目：
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。


示例：
输入：[3,1,2]
输出：9
解释：子数组为 [3]，[1]，[2]，[3,1]，[1,2]，[3,1,2]。 
最小值为 3，1，2，1，1，1，和为 9。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000

第一种写法：

 1 public static long sumSubArrayMin(int[] ary) {
 2         long sum = 0;
 3         for (int i = 1; i <= ary.length; i++) {
 4             for (int j = 0; j < ary.length - i + 1; j++) {
 5                 int[] subAry = new int[i];
 6                 System.arraycopy(ary, j, subAry, 0, i);
 7                 int min = subAry[0];
 8                 for (int k : subAry) {
 9                     if (k < min) {
10                         min = k;
11                     }
12                 }
13                 sum += min;
14             }
15         }
16         return Math.floorMod(sum, (long) (Math.pow(10, 9) + 7));
17 }
知识兔View Code

代码中使用了系统数组复制方法取连续子数组，会增加临时存储空间开销。

第二种写法：优化取子数组最小值

public static long sumSubArrayMin(int[] ary) {
        long sum = 0;
        
        //第一层循环 取连续子数组长度
        for (int i = 1; i < ary.length + 1; i++) {
            
            //第二层循环 每次从数组的第一个数据开始 到数组长度减去子数组长度 + 1
            for (int j = 0; j < ary.length - i + 1; j++) {
                int min = ary[j];//取第一个数作为最小数
                
                //循环取数判断子数组最小数
                for (int k = 0; k < i; k++) {
                    if (ary[j + k] < min) {
                        min = ary[j + k];
                    }
                    System.out.print(ary[j + k] + " ");
                }
                 System.out.println("->" + min);
                sum += min;
            }
        }
        return Math.floorMod(sum, (long) (Math.pow(10, 9) + 7));
    }
}
知识兔View Code

这样写减小了临时存储空间开销及数据复制

根据题目提示

1 <= A <= 30000
1 <= A[i] <= 30000

即数组中最大值可能为30000，最小值可能为1

这样可以把min每次循环取数组时复制为30001，在方法开始定义即可。这样又可以节约一部分临时变量开销。

计算机