O(n) Monostack with picture
I came up with 3 different solutions for this problem, but they did not work (WA or TLE). I got the intuition that we need a monostack, but somehow it was hard 
I came up with 3 different solutions for this problem, but they did not work (WA or TLE). I got the intuition that we need a monostack, but somehow it was hard for me to comprehend.\n\nWe store elements in a stack `st` in a non-decreasing order. When we need to remove an element `j` from the stack, it means:\n- Elements from `j` to `i - 1` are all greater than `j`.\n- Elements after the new top of the stack iare all greater than `j`.\n\nTherefore, we can multiply the current element `j` to the sum of all elements between the new top of the stack and `i`. In the example shown on the following picture, you can see that when we remove element `4` from the stack, we sum numbers between `1` (new top of the stack) and `2` (which is `i`).\n\n![image](https://assets.leetcode.com/users/images/b00b2dd4-b795-4ca1-a0c3-902cf3b7559c_1620686543.4356697.png)\n\nFinally, we use a partial sum array `dp` to efficiently compute sum between elements `j` and `i`.\n\n**C++**\nTo make it simple, we will store indexes of elements, as we can get their values from the original array. Note that we remove all remaining elements from the stack when `i = n.size()` in the second loop.\n\n```cpp\nint maxSumMinProduct(vector<int>& n) {\n    long res = 0;\n    vector<long> dp(n.size() + 1), st;\n    for (int i = 0; i < n.size(); ++i)\n       dp[i + 1] = dp[i] + n[i];\n    for (int i = 0; i <= n.size(); ++i) {\n        while (!st.empty() && (i == n.size() || n[st.back()] > n[i])) {\n            int j = st.back();\n            st.pop_back();\n            res = max(res, n[j] * (dp[i] - dp[st.empty() ? 0 : st.back() + 1]));\n        }\n        st.push_back(i);\n    }\n    return res % 1000000007;\n}\n```\n**Java**\n```java\npublic int maxSumMinProduct(int[] n) {\n    Stack<Integer> st = new Stack<>();\n    long dp[] = new long[n.length + 1], res = 0;\n    for (int i = 0; i < n.length; ++i)\n       dp[i + 1] = dp[i] + n[i];\n    for (int i = 0; i <= n.length; ++i) {\n        while (!st.empty() && (i == n.length || n[st.peek()] > n[i])) {\n            int j = st.pop();\n            res = Math.max(res, (dp[i] - dp[st.empty() ? 0 : st.peek() + 1]) * n[j]);\n        }\n        st.push(i);\n    }\n    return (int)(res % 1000000007);\n}\n```
['C', 'Java']