C++ O(n) solution | Nearest Smaller Element + Prefix Sum | Explained
class Solution {\n\npublic:\n    const int mod = 1e9 + 7;\n    \n    // inutition: for a given i we can include those elements in the subarray which are greater
class Solution {\n\npublic:\n    const int mod = 1e9 + 7;\n    \n    // inutition: for a given i we can include those elements in the subarray which are greater than or equal to nums[i] , in this case the\n\t//resuling min array product will be maximum, hence we can compute this for all i\'s , now to compute the \n\t//given range (l, r) we need to find the nearest smallest element to the left and nearest smallest element to the right\n\t//which can be done using stack , and we can precomput this for all the elements using stack and array, rest is how we can get the sum in the range \n\t//using prefix sum technique (do make sure indexing is 1-based else it causes a lot of problems).\n    \n    \n    // steps to get it done: \n    // 1) understand finding nearest element to the left\n    // 2) understand finding nearest element to the right\n    // 3) finding sum of the range using prefix sum technique\n    int maxSumMinProduct(vector<int> &nums)\n    {\n        int n = (int)nums.size();\n        \n        vector<long long int> prefix(n + 1, 0); // for computing the prefix sum\n        vector<int> left(n, 0);// for computing nearest smaller element to the left\n        vector<int> right(n, 0);// for computing nearest smaller element to the right\n        \n        stack<int> s;\n        \n        for(int i = 0; i < n; i++)\n        {\n            while(s.size() > 0 && nums[s.top()] >= nums[i])\n            {\n                s.pop();\n            }\n            if(s.size() > 0)\n            {\n                left[i] = s.top();\n            }\n         // if at the moment stack gets empty it means there is no element smaller left to it\n        // so we can say element at -1 th position is smaller than ith element\n            else\n                left[i] = -1;\n            s.push(i);\n        }\n        \n        while(s.size() > 0)\n            s.pop();\n        for(int i = n - 1; i >= 0 ;i--)\n        {\n            while(s.size() > 0 && nums[s.top()] >= nums[i])\n            {\n                s.pop();\n            }\n            \n            if(s.size() > 0)\n            {\n               right[i] = s.top();\n            }\n            // if at the moment stack gets empty it means there is no element smaller right to it\n            // so we can say element at nth position is smaller that ith element\n            else\n                right[i] = n;\n            s.push(i);\n        }\n        \n   \n        for(int i = 1; i <= n; i++)\n            prefix[i] = prefix[i - 1] + nums[i - 1];\n        \n        long long int maxSum = 0, currSum = 0;\n        \n        for(int i = 0; i < n; i++)\n        {\n            currSum = nums[i] * 1LL * (prefix[right[i]] - prefix[left[i] + 1]);\n            maxSum = max(maxSum, currSum);\n        }\n        return maxSum % mod;\n    }\n};\n
[]