Monostack, prefix sum - Concise C++ solution
\n# Code\n\nclass Solution\n{\npublic:\n    int maxSumMinProduct(vector<int> &n)\n    {\n        // Initialize a variable \'res\' to store the maximum sum of th
\n# Code\n```\nclass Solution\n{\npublic:\n    int maxSumMinProduct(vector<int> &n)\n    {\n        // Initialize a variable \'res\' to store the maximum sum of the subarray\n        long res = 0;\n        // Create a vector \'dp\' to store the prefix sums of the input vector \'n\'\n        vector<long> dp(n.size() + 1);\n        // Create a vector \'st\' to store the indices of the integers in \'n\' that are used to calculate the maximum sum\n        vector<long> st;\n        // Calculate the prefix sums of the input vector \'n\' and store them in the \'dp\' vector\n        for (int i = 0; i < n.size(); ++i)\n        {\n            dp[i + 1] = dp[i] + n[i];\n        }\n        // Iterate through the input vector \'n\'\n        for (int i = 0; i <= n.size(); ++i)\n        {\n            // While the \'st\' vector is not empty and the current integer in \'n\' is greater than or equal to the last integer in \'st\'\n            while (!st.empty() && (i == n.size() || n[st.back()] > n[i]))\n            {\n                // Pop the last integer in \'st\' and store it in the variable \'j\'\n                int j = st.back();\n                st.pop_back();\n                // Update the maximum sum of the subarray by calculating the sum of the subarray between the last element in \'st\' and the current element \'i\'\n                // and multiplying it by the value of the popped integer \'j\'\n                res = max(res, n[j] * (dp[i] - dp[st.empty() ? 0 : st.back() + 1]));\n            }\n            // Push the current index \'i\' into the \'st\' vector\n            st.push_back(i);\n        }\n        // Return the maximum sum of the subarray mod 1000000007 to prevent overflow\n        return res % 1000000007;\n    }\n};\n```\n\n# Code without comments\n```\nclass Solution {\npublic:\n    int maxSumMinProduct(vector<int>& n) {\n        long res = 0;\n        vector<long> dp(n.size() + 1), st;\n        for (int i = 0; i < n.size(); ++i)\n        dp[i + 1] = dp[i] + n[i];\n        for (int i = 0; i <= n.size(); ++i) {\n            while (!st.empty() && (i == n.size() || n[st.back()] > n[i])) {\n                int j = st.back();\n                st.pop_back();\n                res = max(res, n[j] * (dp[i] - dp[st.empty() ? 0 : st.back() + 1]));\n            }\n            st.push_back(i);\n        }\n         return res % 1000000007;\n    }\n};\n\n```\n\n\nDO UPVOTE!
['Stack', 'Monotonic Stack', 'Prefix Sum', 'C++']