Stack | Prefix Sum Technique
Approach : \n1. For every element at index i, find the next smaller element\'s index and previous smaller element\'s index. This will  give us an idea about the
**Approach** : \n1. For every element at index **i**, find the next smaller element\'s index and previous smaller element\'s index. This will  give us an idea about the **size of the subarray in which ith element is minimum**. \n2. Now since we know the boundary of the subarray in which ith element in minimum  , **we can query for the sum of this subarray** and **multiply it with** ith **element** and track the maximum answer.   \n3. To query the subarray sum, we will take a prefix sum and then answer the query in O(1). \n\n**Time Complexity**:\n* Prefix sum pre-calculation O(N)\n* Finding next smaller element for every element : O(N) \n* Finding previous smaller element for every element : O(N) \n* Calculating the answer , considering every ith element as minimum : O(N)\n**Overall : O(N)**\n\n**Space Complexity**: O(N)\n\n**Note** : Take care of overflows  , use long long int wherever necessary. \n\n##### Code \n```\n#define cmax(x,y)         (x >= y ? x : y)\n\nclass Solution {\npublic:\n\tvector<int> nextSmallerElement(vector<int>& arr, int n) {\n\t\tvector<int> ans(n);\n\t\tstack < int > stk;\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\twhile (!stk.empty() && arr[stk.top()] > arr[i]) {\n\t\t\t\tans[stk.top()] = i;\n\t\t\t\tstk.pop();\n\t\t\t}\n\t\t\tstk.push(i);\n\t\t}\n\t\twhile (!stk.empty()) {\n\t\t\tans[stk.top()] = n;\n\t\t\tstk.pop();\n\t\t}\n\t\treturn ans;\n\t}\n\tvector<int> prevSmaller(vector<int> &A) {\n\t\tvector<int> ans;\n\t\tans.resize(A.size());\n\t\tstack<int> st;\n\t\tfor (int i = 0; i < A.size(); i++) {\n\t\t\twhile (!st.empty() && A[st.top()] >= A[i]) st.pop();\n\t\t\tif (st.empty()) {\n\t\t\t\tans[i] = -1;\n\t\t\t} else {\n\t\t\t\tans[i] = st.top();\n\t\t\t}\n\t\t\tst.push(i);\n\t\t}\n\t\treturn ans;\n\t}\n\tint maxSumMinProduct(vector<int>& nums) {\n\t\tvector<int> a = nextSmallerElement(nums, nums.size());\n\t\tvector<int> b = prevSmaller(nums);\n\t\tvector<long long int> pref(nums.size());\n\t\tpref[0] = nums[0];\n\t\tfor (int i = 1; i < nums.size(); i++)\n\t\t\tpref[i] = pref[i - 1] + nums[i];\n\t\tlong long ans = LLONG_MIN;\n\t\tfor (int i = 0; i < nums.size(); i++) {\n\t\t\tint x = b[i] + 1;\n\t\t\tint y = a[i] - 1;\n            if(x==0)\n                ans = cmax(ans, nums[i] * (pref[y]));\n\t\t\telse ans = cmax(ans, nums[i] * (pref[y] - pref[x - 1]));\n\t\t}\n\t\treturn ans % 1000000007;\n\t}\n};\n```\n\n
[]