@@ -0,0 +1,2210 @@
+//  Copyright 2019 The KeepTry Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage dp;%0A%0Aimport java.util.Arrays;%0Aimport java.util.Stack;%0A%0A/**%0A * %3Cpre%3E%0A * Given an array of integers A, find the sum of min(B),%0A * where B ranges over every (contiguous) subarray of A.%0A *%0A * Since the answer may be large, return the answer modulo 10%5E9 + 7.%0A *%0A *%0A *%0A * Example 1:%0A *%0A * Input: %5B3,1,2,4%5D%0A * Output: 17%0A * Explanation: Subarrays are %5B3%5D, %5B1%5D, %5B2%5D, %5B4%5D, %5B3,1%5D, %5B1,2%5D, %5B2,4%5D, %5B3,1,2%5D, %5B1,2,4%5D, %5B3,1,2,4%5D.%0A * Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.%0A *%0A *%0A * Note:%0A *%0A * 1 %3C= A.length %3C= 30000%0A * 1 %3C= A%5Bi%5D %3C= 30000%0A *%0A *%0A *%0A */%0Apublic class Leetcode907SumOfSubarrayMinimums %7B%0A%0A    public static int sumSubarrayMins(int%5B%5D A) %7B%0A        if (A == null %7C%7C A.length == 0) return 0;%0A%0A        double%5B%5D dp = new double%5BA.length%5D;%0A        // monotonously increasing index stack%0A        Stack%3CInteger%3E stack = new Stack%3C%3E();%0A%0A        // init%0A        dp%5B0%5D = A%5B0%5D;%0A        stack.push(0);%0A%0A        for (int i = 1; i %3C A.length; i++) %7B%0A            while (!stack.empty() && A%5Bi%5D %3C= A%5Bstack.peek()%5D) %7B%0A                stack.pop();%0A            %7D%0A%0A            if (stack.empty()) %7B%0A                dp%5Bi%5D = A%5Bi%5D * (i + 1);%0A            %7D else %7B%0A                int j = stack.peek();%0A                dp%5Bi%5D = A%5Bi%5D * (i - j) + dp%5Bj%5D;%0A            %7D%0A%0A            // for next%0A            stack.push(i);%0A        %7D%0A%0A        return (int) (Arrays.stream(dp).sum() %25 (Math.pow(10, 9) + 7));%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        System.out.println(sumSubarrayMins(new int%5B%5D %7B3, 1, 2, 4%7D) == 17);%0A        System.out.println(sumSubarrayMins(new int%5B%5D %7B51, 29%7D) == 109);%0A    %7D%0A%7D%0A

DP+monotonic stack: Leetcode 907. Sum of Subarray Minimums