JAVA算法：子数组的最小和

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])) （1<=i<=n）

算法设计

private static Double MOD = Math.pow(10, 9) + 7;
	
	public int sumSubarrayMins(int[] nums) {
        if (nums.length == 1) {
        	return nums[0];
        }
        
        int len = nums.length;
        int[] dp = Arrays.copyOf(nums, nums.length);
        for (int i = 1; i < len; i++) {
            int temp = 0;
            int minValue = nums[i];
            for (int j = i; j >= 0; j--) {
            	minValue = Math.min(minValue, nums[j]);
                temp = temp + minValue;
            }
            int a = dp[i - 1] + temp;
            dp[i] = (int) (a % MOD);
        }
        return (dp[len - 1]);
    }

结果提交时，超过了97%的用例，但是最终还是算法超时（Time Limit Exceeded）。

Accepted的算法：

public int sumSubarrayMins(int[] nums) {

		int res = 0;
		int[] rdp = new int[nums.length];
		int[] ldp = new int[nums.length];

		for (int i = nums.length - 1; i >= 0; i--) {
			rdp[i] = i + 1;
			while (rdp[i] < nums.length && nums[rdp[i]] > nums[i])
				rdp[i] = rdp[rdp[i]];
		}

		for (int i = 0; i < nums.length; i++) {
			ldp[i] = i - 1;
			while (ldp[i] >= 0 && nums[ldp[i]] >= nums[i])
				ldp[i] = ldp[ldp[i]];
		}

		for (int i = 0; i < nums.length; i++) {
			int j = ldp[i] + 1, k = rdp[i] - 1;
			res = (res + (k - j + 1 + (k - i) * (i - j)) * nums[i]) % 1000000007;
		}
		return res;

}

提交结果：

使用Stack的算法设计

public int sumSubarrayMins(int[] nums) {

		Stack<Integer> s = new Stack<>();
		int n = nums.length;
		int res = 0;
		int mod = (int) 1e9 + 7;
		int j;
		int k;
		for (int i = 0; i <= n; i++) {
			while (!s.isEmpty() && nums[s.peek()] > (i == n ? 0 : nums[i])) {
				j = s.pop();
				k = s.isEmpty() ? -1 : s.peek();
				res = (res + nums[j] * (i - j) * (j - k)) % mod;
			}
			s.push(i);
		}
		return res;
	}