Easy to understand || Commented || O(N) || CPP
\nint maxSumMinProduct(vector<int>& nums) {\n    int n = nums.size();\n\n    // LeftMost[i] represent the farthest element which is greater than or equal to num
```\nint maxSumMinProduct(vector<int>& nums) {\n    int n = nums.size();\n\n    // LeftMost[i] represent the farthest element which is greater than or equal to nums[i] in left side\n    // rightMost[i] represent the farthest element which is greater than or equal to nums[i] in right side\n\n    vector<int> leftMost(n), rightMost(n);\n\n    vector<long long int> sum(n + 1);\n\n    sum[0] = 0;\n    stack<int> st;\n    for (int i = 0; i < n; i++) {\n        sum[i + 1] = sum[i] + nums[i];\n\n        // Find farthest\n        while (st.size() && nums[st.top()] >= nums[i]) st.pop();\n        if (st.size()) {\n            leftMost[i] = st.top() + 1;\n        } else {\n            // This is the largest till now\n            leftMost[i] = 0;\n        }\n        st.push(i);\n    }\n\n    while (st.size()) st.pop();\n\n    for (int i = n - 1; i >= 0; i--) {\n        // Find farthest from right side\n        while (st.size() && nums[st.top()] >= nums[i]) st.pop();\n        if (st.size()) {\n            rightMost[i] = st.top() - 1;\n        } else {\n            // This is largest for right side till now\n            rightMost[i] = n - 1;\n        }\n        st.push(i);\n    }\n\n    long long ans = 0;\n\n    // let\'s suppose each nums[i] is the minimum\n    for (int i = 0; i < nums.size(); i++) {\n        ans = max(ans, (long long)nums[i] * (sum[rightMost[i] + 1] - sum[leftMost[i]]));\n    }\n    return ans % 1000000007;\n}\n```
[]