C++ | TC: O(N) | SC: O(N)
Feel free to post your doubts in comment section\n# Stacks | Prefix Sum | Next Min on Left & Right\n For every element we will try to find the best ans, i.e. co
# Feel free to post your doubts in comment section\n# Stacks | Prefix Sum | Next Min on Left & Right\n* For every element we will try to find the best ans, i.e. considering every ith element as minimum, how much we can extend the subarray to left and right ?\n*This made me to find left and right minimum*\n\n* Now we can find the subarray sum between left min and right min index, how to optimise this ? \n*This made me to go for prefix sum.*\n\nGive it a like if it helped you !\n```\nclass Solution {\npublic:\n    void nextMinOnLeft( vector<int>& A, vector<int> &leftMin){ \n        stack<int> s;\n        int n=A.size();\n        for( int i=n-1; i>=0; i-- ){\n            while( !s.empty() && A[s.top()] > A[i] ){\n                leftMin[s.top()] = i;\n                s.pop();\n            }\n            s.push(i);\n        }\n    }\n    void nextMinOnRight( vector<int>& A, vector<int> &rightMin ){\n        stack<int> s;\n        int n=A.size();\n        for( int i=0; i<n; i++ ){\n            while( !s.empty() && A[s.top()] > A[i] ){\n                rightMin[s.top()] = i;\n                s.pop();\n            }\n            s.push(i);\n        }\n    }\n    int maxSumMinProduct(vector<int>& nums) {\n        int n =nums.size();\n        vector<long long> ps( n, 0 );\n        vector<int> leftMin( n, -1 );\n        vector<int> rightMin( n, n );\n        nextMinOnLeft( nums, leftMin );\n        nextMinOnRight( nums, rightMin );\n        for(int i=0; i<n; i++){\n            if(i==0){ps[i]=nums[0]; continue;}\n            ps[i] = ps[i-1]+nums[i];\n        }\n        long long ans = 0;\n        for(int i=0; i<n; i++){\n            int lm = leftMin[i];\n            int rm = rightMin[i];\n            long long temp = 1ll*nums[i]*(1ll)*( ps[rm-1]-ps[lm+1]+nums[lm+1] );\n            ans = max( ans, temp );\n        }\n        ans%=1000000007;\n        return ans;\n    }\n};\n```
[]