20ms, prefix sum + monotonic stack with clear explanation
ApproachTo find a maximum product of subarray's sum and minimum subarrays's item, we need to be able quickly answer on two questions:
For each item of array, wh
# Approach
To find a maximum product of subarray's sum and minimum subarrays's item, we need to be able quickly answer on two questions:

1. For each item of array, which items should be the bounds of subarray, where the current item is a minimum?
2. How to find a sum of any subarray?

Answering question one, we come up with a problem of finding previous lower item both to the right and to the left. Statement "next lower (greater) item" is a great sign for using a monotonic stack. If you're not familiar with monotonic stack, first try to solve (or check the editorial) the problem: https://leetcode.com/problems/next-greater-element-i.

Answering question two, a common way to find a sum of a subarray is using prefix sum array. To understand and practice prefix sum technique, try to solve this problem first (or use editorial): https://leetcode.com/problems/range-sum-query-immutable.

So, the solution of the problem is to precalculate prefix sums, as well as indices of the next lower and previous lower items in the array of each item. After we do these calculations, we can quickly get a subarray, where the current item is a minimum one, get its sum using the prefix sum array and multiply it by the value of the current item.

# Complexity
- Time complexity:

Construct prefix sums array: **O(n)**
Construct an array of previous lower items: **O(n)**
Construct an array of next lower items: **O(n)**
Iterate throught array and calculate a product of the subarray where the current item in minimal: **O(n)**

Overall: O(4*n) = **O(n)**

- Space complexity:

We need three arrays (for prefix sums, next lower items and previous lower items) additionally, each sile of **n**. Also, a stack we're using to calculate next and previous lower items can't be larger than **n**. So, the space complexity would be O(4*n) = **O(n)**

# Code
```golang []
func maxSumMinProduct(nums []int) int {
    // Construct a prefix sum
    prefixes := make([]int, len(nums))
    prefixes[0] = nums[0]
    for i:=1; i<len(nums); i++ {
        prefixes[i] = nums[i] + prefixes[i-1]
    }

    // Construct a previous lower index array
    prevLowers := make([]int, len(nums))
    st := make([]int, 0)
    for i:=range nums {
        for len(st) > 0 && nums[i] <= nums[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            prevLowers[i] = -1
        } else {
            prevLowers[i] = st[len(st)-1]
        }
        st = append(st, i)
    }

    // Construct a next lower index array
    nextLowers := make([]int, len(nums))
    st = make([]int,0)
    for i:=len(nums)-1; i>=0; i-- {
        for len(st) > 0 && nums[i] <= nums[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            nextLowers[i] = len(nums)
        } else {
            nextLowers[i] = st[len(st)-1]
        }
        st = append(st, i)
    }

    // Find a maximum product for each subarray, 
    // where the current item is  minimal.
    var res int64
    for i:=range nums {
        curRes := prefixes[nextLowers[i]-1]
        if prevLowers[i] != -1 {
            curRes -= prefixes[prevLowers[i]]
        }

        res = max(res, int64(curRes)*int64(nums[i]))
    }

    return int(res % (1e9+7))
}
```
['Monotonic Stack', 'Prefix Sum', 'Go']