当前位置: 代码迷 >> 综合 >> JAVA算法:子数组的最小和
  详细解决方案

JAVA算法:子数组的最小和

热度:66   发布时间:2024-01-15 19:38:57.0

JAVA算法:子数组的最小和

给定一个整数数组 A,找到 min(B) 的总和,其中 B 的范围为 A 的每个(连续)子数组。

例如:给定数组 A为 [3,1,2,4]
输出:17
解释:数组A的子数组为: [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]。 
对于以上10个子数组,每个子数组即为B,那么每个子数组中的最小元素分别为: 3,1,2,4,1,1,2,1,1,1,其和为 17。

由于答案可能很大,因此返回答案模 10^9 + 7。 

注意:

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

算法分析

先设定常量MOD为:

private static Double MOD = Math.pow(10, 9) + 7;

如果数组A的长度为1,则返回数组中的唯一一个元素。

采用动态规划思路求解时,状态方程为:

f[n] = f[n-1]+sum(min(A[i~n])) ?