C++ simple solution using union-find O(n) || Explained
So what we do is \n\n Calculating all sub arrays and finding their min gives us TLE\n So what we do is,\n we consider nums[i] where 0<=i< n, as min element and 
So what we do is \n\n* Calculating all sub arrays and finding their min gives us TLE\n* So what we do is,\n* we consider nums[i] where 0<=i< n, as min element and find the min-products of subarrays with minimum as nums[i].\n* First we compute and store the prefix sum of given array.\n* Then for every nums[i] for 0<=i<n\n* We find the index of the first element smaller than nums[i] in the left subarray and store it in **left** and the index of the first smaller element in the right subarray and store it in **right**.\n\n   for array [3,1,5,6,4,2] : pre_sum = [3, 4, 9, 15, 19, 21] , left = [-1, -1, 1, 2, 1, 1] , right = [6, 5, 4, 4, 6, 1]\n   \n* Now, we just traverse the array and for every nums[i] where 0<=i<n we calculate the min-product and store in res and maximum of them is stored in gmax.\n* return gmax % 1000000007\n\n   PLEASE UPVOTE IF YOU FIND IT HELPFUL!\n   \n   C++ Code:\n   \n```\nclass Solution {\npublic:\n#define lli long long int\n    \n    int findmin(int idx, int cur, vector<int>& minidx, vector<int>& n){  \n        if(idx == -1 || idx == n.size())\n            return idx;\n        if(n[idx] < n[cur])\n            return idx;\n        \n        return findmin(minidx[idx], cur, minidx, n);\n            \n    }\n    int maxSumMinProduct(vector<int>& n){\n        \n        int sz = n.size();\n        lli sum[sz];\n        vector<int> left(sz), right(sz);\n        \n        sum[0] = n[0];\n        \n        for(int i=1;i<n.size();i++)\n            sum[i] = sum[i-1]+n[i];\n        \n        for(int i=0;i<sz;i++)\n            left[i] = findmin(i-1, i, left, n);\n        \n        for(int i=sz-1;i>=0;i--)\n            right[i] = findmin(i+1, i, right, n);\n        \n        lli gmax = INT_MIN;\n        lli res;\n        for(int i=0;i<sz;i++){\n            res = (sum[right[i]-1] - (left[i]>=0?sum[left[i]]:0)) * n[i];\n            gmax = max(gmax,res);\n        }\n        \n        return gmax%1000000007;\n    }\n};\n```\n\n
['Union Find', 'C']