Should be marked as Hard. O(n) solution
It is similar problem to Largest Rectangle in Histogram. First solve it, then it will be easy.\nhttps://leetcode.com/problems/largest-rectangle-in-histogram/\n\
It is similar problem to Largest Rectangle in Histogram. First solve it, then it will be easy.\nhttps://leetcode.com/problems/largest-rectangle-in-histogram/\n```\n\tint maxSumMinProduct(vector<int>& nums)\n    {\n        stack<int> st;\n        int mod = 1e9 + 7;\n        nums.push_back(0);\n        vector<long long int> vec(nums.size()+1);\n        long long int max_sum = 0;\n        \n        for(int i = 0;i < nums.size();i++)\n        {\n            vec[i+1] = vec[i] + nums[i]; \n        }\n        int i = 0;\n        \n        while(i < nums.size())\n        {\n            if(!st.size() or nums[i] >= nums[st.top()]) st.push(i++);\n            else\n            {\n                int mid_d = nums[st.top()];\n                st.pop();\n                int j = st.size() ? st.top():-1;\n                if(max_sum < mid_d*(vec[i] - vec[j+1])) max_sum = mid_d*(vec[i] - vec[j+1]);\n            }\n        }\n        return max_sum%mod;\n    }\n```
[]