C++ O(N) Stack Solution
Runtime: 243 ms, faster than 83.17% of C++ online submissions for Maximum Subarray Min-Product.\nMemory Usage: 83.6 MB, less than 81.25% of C++ online submissio
Runtime: 243 ms, faster than 83.17% of C++ online submissions for Maximum Subarray Min-Product.\nMemory Usage: 83.6 MB, less than 81.25% of C++ online submissions for Maximum Subarray Min-Product.\n\n```\nNeed to maintain a monotone increasing order using Stack to find each potential max\nvalues which are at the top of the Stack until smaller value of nums[i] appears at top.\n\nEach max top values can have subarray from previous min value (Stack next top value )\nto current min value (nums[i]).\n\nMin value max product =>  nums[Stack.top()] * Sum between previous min and current min value.\n\nPrefix sum array can provide the range sum from previous min to current min.\n```\n\n\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& nums) {\n        \n        int n = nums.size();\n        vector<long long>prefixSum(n);\n        \n        // store prefix sum of the given array\n        prefixSum[0] = nums[0];\n        for(int i=1;i<n;i++)\n            prefixSum[i]+=prefixSum[i-1]+nums[i];\n        \n        long long res = 0L;\n        long long curr;\n        long long sum;\n        int index;\n        stack<int>stak;    // monote stack\n        \n        for(int i=0;i<=n;i++)\n        {\n            // for each current value loop until stak is empty or previous min value is found\n            // stak top values are potential max values who\'s previous min value is in the stak\n            // so the product => potential max value * prefixSum[previous min value to current value]\n            // also at last until stak is empty process all the values\n            while(!stak.empty() && (i==n || nums[stak.top()]>nums[i]))\n            {\n                index = stak.top();\n                stak.pop();\n                curr = nums[index];\n                \n                // sum between previous min value and current value\n                sum = (prefixSum[i-1] - (stak.empty() ? 0 : prefixSum[stak.top()]));\n                \n                // update max product\n                res = max(res, curr * sum);                 \n            }   \n\n            rightStak.push(i);\n        }\n\n        return res % 1000000007;\n    }\n};\n```
['Stack', 'C', 'Prefix Sum']