C++ O(N) Time. Next Smaller Element
See my latest update in repo LeetCode\n\n## Solution 1. Next Smaller Element\n\nIntuition: For a given number A[i], we only care about the subarray [p + 1, q - 
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Next Smaller Element\n\n**Intuition**: For a given number `A[i]`, we only care about the subarray `[p + 1, q - 1]` where `p` and `q` are the index to the previous and next smaller element.\n\n\n**Why do we use the next/previous smaller element as the boundary?**:\nFor example:\n\n```\n 0 1 2 3 4 5 // index\n[3,1,5,6,4,2] // value\n```\n\nFor `A[1] = 1`, it\'s the smallest value of the entire array. So we should use the sum of the entire array.\n\nFor `A[5] = 2`, it\'s the second smallest value. We won\'t want to extend the subarray to index `1` because then the minimum value will become `1` and fall back to the previous case. So we only use subarray `[5,6,4,2]`.\n\nSimilarly, for other numbers. In essense, we don\'t want to go over the previous/next smaller element.\n\n**Algorithm**:\n\n1. Store prefix sum in `sum` array.\n2. Store the indexes to the previous/next smaller element into `prev`/`next` array. \n3. For `A[i]`, the max product including it is `A[i] * SUM(prev[i] + 1, next[i] - 1)` where `SUM(i, j)` is the sum of subarray `A[i..j]`.\n\nFor "how to get the next smaller element", check out the mono-stack solutions to [496. Next Greater Element I (Easy)](https://leetcode.com/problems/next-greater-element-i/)\n\n```cpp\n// OJ: https://leetcode.com/problems/maximum-subarray-min-product/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& A) {\n        long long mod = 1e9+7, N = A.size(), ans = 0;\n        vector<long long> sum(N + 1); // prefix sum\n        for (int i = 0; i < N; ++i) sum[i + 1] = sum[i] + A[i];\n        vector<int> prev(N, -1), next(N, -1); // prev[i]/next[i] is the index to the previous/next smaller element\n        vector<int> s; // a stack.\n        for (int i = 0; i < N; ++i) { // compute the index to the previous smaller elements\n            while (s.size() && A[s.back()] >= A[i]) s.pop_back();\n            if (s.size()) prev[i] = s.back();\n            s.push_back(i);\n        }\n        s.clear();\n        for (int i = N - 1; i >= 0; --i) { // compute the index to the next smaller elements\n            while (s.size() && A[s.back()] >= A[i]) s.pop_back();\n            if (s.size()) next[i] = s.back();\n            s.push_back(i);\n        }\n        for (int i = 0; i < N; ++i) {\n            long long s = next[i] == -1 ? sum.back() : sum[next[i]];\n            if (prev[i] != -1) {\n                s -= sum[prev[i] + 1];\n            }\n            ans = max(ans, (long long) A[i] * s);\n        }\n        return ans % mod;\n    }\n};\n```
[]