Sum of Subarray Minimums

class Solution {
    public int minimumSumSubarrays(int[] numbers) {
        final int MODULO = 1000000007;

        Stack<Integer> indexStack = new Stack<>();

        // we use a dynamic programming table `resultValues`
        int[] resultValues = new int[numbers.length];

        // Process each element for constructing minimum sum subarrays
        for (int idx = 0; idx < numbers.length; idx++) {
            // Maintain indices in the stack such that their corresponding values are increasing
            while (!indexStack.isEmpty() && numbers[indexStack.peek()] >= numbers[idx]) {
                indexStack.pop();
            }

            if (!indexStack.isEmpty()) {
                int previousIndex = indexStack.peek();
                resultValues[idx] = resultValues[previousIndex] + (idx - previousIndex) * numbers[idx];
            } else {
                resultValues[idx] = (idx + 1) * numbers[idx];
            }
            // Push current index for further reference
            indexStack.push(idx);
        }

        // Compute the sum using the `resultValues` with modulo operation
        long sumOfMinSubarrayVals = 0;
        for (int value : resultValues) {
            sumOfMinSubarrayVals += value;
            sumOfMinSubarrayVals %= MODULO;
        }

        return (int) sumOfMinSubarrayVals;
    }
}

The given code in Java implements a method to compute the sum of minimums of all subarrays within an array, using stacks and dynamic programming, and then returns the sum modulo (10^9 + 7). Here's an overview of the approach and how the elements of the code achieve the desired functionality:

• Initialization:

  • Define a constant MODULO with a value of (10^9 + 7).
  • Use a stack, indexStack, to remember indices of array elements in a particular order.
  • An integer array, resultValues, stores interim results.

• Process Each Element:

  • Loop through each element in the input array numbers using a for-loop.
  • Ensure elements in indexStack have increasing values corresponding to their indices. If a current element is less than the element at the top of the stack, pop the stack.

• Dynamic Programming Calculation:

  • If the stack is not empty, calculate the result for the current index based on the previously stored value and the distance from the last index in the stack and the current element's value.
  • If the stack is empty, the calculation is straightforward using the current index and the element's value.
  • Push the current index to the stack for future reference.

• Sum Up Results:

  • Initialize a long variable sumOfMinSubarrayVals to accumulate the values from resultValues.
  • Iterate over resultValues, adding each value to sumOfMinSubarrayVals and reduce it modulo MODULO.

• Return Result:

  • Convert sumOfMinSubarrayVals to an integer and return it.

This implementation takes advantage of the properties of stacks to efficiently track necessary indices and uses dynamic programming to store intermediate results, optimizing the computation of the required sum.

let calculateMinimumsSum = function (inputArray) {
    const MODULO = 1000000007;
    let increasingStack = [];
    let dpArray = new Array(inputArray.length).fill(0);

    for (let index = 0; index < inputArray.length; index++) {
        while (increasingStack.length && inputArray[increasingStack.at(-1)] >= inputArray[index]) {
            increasingStack.pop();
        }

        if (increasingStack.length) {
            const previousSmallerIndex = increasingStack.at(-1);
            dpArray[index] = dpArray[previousSmallerIndex] + (index - previousSmallerIndex) * inputArray[index];
        } else {
            dpArray[index] = (index + 1) * inputArray[index];
        }
        increasingStack.push(index);
    }

    const resultSum = dpArray.reduce((total, current) => total + current, 0);

    return resultSum % MODULO;
};

The supplied JavaScript function calculateMinimumsSum efficiently computes the sum of the minimum values of all subarrays given an input array, employing an algorithm that uses dynamic programming in combination with a stack to achieve optimized performance. This technique is particularly useful for handling large datasets where naive approaches might fail due to excessive computational time or memory usage.

Function Overview:

• Initialize constants and data structures:

  • MODULO: A constant to ensure the sum remains within a manageable range, avoiding overflow issues by returning the sum modulo 1000000007.
  • increasingStack: A stack that will store indices of the array elements in increasing order.
  • dpArray: An array to store intermediate results, where each element represents the sum of the minimums for all subarrays ending at that index.

• Iterate over each element in the input array:

  • Use the stack to maintain a list of indices where array elements are in increasing order. Pop elements from the stack that are not less than the current element to maintain the order.
  • For each element at the current index, calculate the contribution to the sum based on the previous elements that are smaller:
    • If there are elements in the stack, calculate the current index's value in dpArray by adding it to the result from the last smaller element and adjusting for the distance between them.
    • If the stack is empty, calculate using all previous elements since the current element is the smallest encountered so far.
  • Push the current index onto the stack.

• Finally, compute the result as the sum of all entries in dpArray and apply the modulo operation. This sum is the output of the function, representing the sum of all subarray minimums under modular arithmetic.

Key Points to Note:

• MODULO operation ensures that the results are within a standard range, especially important in environments with potential large numbers or in competitive programming contexts.
• Utilizing a stack along with dynamic programming allows the algorithm to operate in linear time, rather than the quadratic time required by simpler, nested loop approaches.
• The function directly modifies and uses the input data structure via indices and stack operations to avoid unnecessary complexity or excessive memory usage.

By breaking down the problem in this systematic way and employing combined strategies from computer science fundamentals, the function strives to deliver a solution that is both efficient and accessible, managing complexity without sacrificing performance.

class MinSubarraySum:
    def calculateSum(self, nums: List[int]) -> int:
        MODULO = 1_000_000_007

        monostack = []
        dp_values = [0] * len(nums)

        for idx in range(len(nums)):
            while monostack and nums[monostack[-1]] >= nums[idx]:
                monostack.pop()

            if monostack:
                last_smaller_idx = monostack[-1]
                dp_values[idx] = dp_values[last_smaller_idx] + (idx - last_smaller_idx) * nums[idx]
            else:
                dp_values[idx] = (idx + 1) * nums[idx]
            monostack.append(idx)

        return sum(dp_values) % MODULO

The Python solution provided defines a class MinSubarraySum with a method calculateSum to compute the sum of subarray minimums for a given list of integers. The method employs an algorithm that involves dynamic programming combined with a monotonous stack approach to efficiently compute the required sum. Here’s an overview of how it operates:

• Initialization: A modulo constant (MODULO) is used to ensure the result stays within the bounds of a large integer value due to constraints typically found in competitive programming problems. An empty list monostack is utilized for stockpiling indices of elements, and dp_values is initialized to store intermediate results.

• Iterative Computation: Each element of the array is individually processed. For each element:

  • The stack is popped until an element less than the current element is encountered or the stack is empty, which helps in maintaining the "min" property in the current subarray context.
  • Depending on whether the stack is empty or not, the dp value for the current index is calculated by considering previously computed results (dp_values[last_smaller_idx]) and the contribution of the current number extended across the subarray ending at the current index ((idx - last_smaller_idx) * nums[idx]).
  • The current index is appended to the stack to be used by subsequent elements.

• Final Computation: The accumulated dp values give the subarray sums, which are totaled and returned modulo MODULO to handle large numbers and prevent overflow. This result represents the sum of the minimums of all possible subarrays within the input list.

The approach ensures efficiency by reducing the complexity typically associated with computing subarray sums individually, leveraging prior computations and properties of monotonous stacks.