[Java] DP Solution, beginner friendly breakdown of intuition and approach, 15 ms, beats 93.5%.
Intuition\n Describe your first thoughts on how to solve this problem. \n Checking all possible subarrays to see if it exceeds the max min product seems incredi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n Checking all possible subarrays to see if it exceeds the max min product seems incredibly inefficient as doing so would take $$O(n^2)$$ checks. There should be some way to optimize selecting potential candidates for the maximum \'min-product\' subarrays and only check those.\n\n## **Every possible subarray contains some minimum value**\n\nSince the nums array only carries n different values, if we can find the most optimal subarray that has a minimum value of nums[i] for all i in nums, the amount of checks goes from $$O(n^2)$$ to $$O(n)$$. \n\n## How can we the optimal subarray for a given minimum value in nums?\nIf we want nums[i] to be the minimum value in the subarray, in order to maximize the \'min-product\', the two elements contributing to the product need to be maximized, namely **the minimum element** in the subarray and **the sum of all the elements**, as the min-product = min element * sum of elements.\n\n#### The minimum element\nDefining every subarray based on the minimum element allows us to effectively ignore this factor, as we are comparing subarrays all with the same minimum value. This allows us to focus on maximizing the sum of all elements.\n\n#### The sum of subarray elements\nSince nums[i] >= 1, every new element in nums that is added to the subarray will increase its sum. Therefore, **maximizing the sum is the same as maximizing the width of the subarray**. \n\n#### Maximizing the width of the subarray\nTo maximize the width of a subarray with a given minimum element, we can expand outward from that element on the left and the right until we find an element less than the selected minimum to the left and to the right of our minimum position.\n\n##### Example: \n\nlet nums = {9 1 2 3 **2** 4 5 8 1 4 9}\nLet the selected subarray minimum be the bolded element (nums[4]), and let l and r denote left and right pointers. Positions at l and r are bolded.\n\nl = 3, r = 5\n9 1 2 **3** 2 **4** 5 8 1 4 9\n      \nl = 2, r = 6\n9 1 **2** 3 2 4 **5** 8 1 4 9\n\nl = 1, r = 7\n9 **1** 2 3 2 4 5 **8** 1 4 9\n\nl = 1, r = 8\n\n9 **1** 2 3 2 4 5 8 **1** 4 9\n\nLesser elements have been found on both sides, so the optimal subarray with the selected minimum is the subarray (l, r) exclusive, or **{2, 3, 2, 4, 5, 8}**\n            \n\n# Approach\n###### Define two arrays: **lessFromLeft** and **lessFromRight**\n```\nint[] lessFromLeft = new int[nums.length];\nint[] lessFromRight = new int[nums.length];\n```\n### lessFromLeft\nlessFromLeft[i] denotes the \'left\' pointer from the width maximization of the subarray with a chosen minimum at index i. In other words, it is the index of the first lower number than nums[i] to the left of nums[i]. \n\n### lessFromRight\nlessFromRight[i] is the same principle but with the index of the first number lower than nums[i] to the right of nums[i].\n```\nint minIndex = //Index of chosen min;\n\nint pLeft = minIndex-1;\nwhile(pLeft >= 0 && nums[pLeft] >= nums[minIndex]) {\n    pLeft--;\n}\nlessFromLeft[minIndex] = pLeft;\n\nint pRight = minIndex+1; \nwhile (pRight < nums.length && nums[pRight] >= nums[minIndex]) {\n    pRight++;\n}\nlessFromLeft[minIndex] = pRight;\n```\nThese calculations can still be further optimized using **dynamic programming** that relies on previous values of the arrays. However, no extra dp space needs to be allocated as said values are already be stored in the arrays themselves. \n\nIf nums[pLeft] >= nums[minIndex], then any values nums[i] >= nums[pLeft] is also >= nums[minIndex]. Therefore **we can skip to the first nums[i] less than nums[pLeft] where i is left of pLeft**. This is the first element less than nums[pLeft] to its left, which is **lessFromLeft[pLeft]**! This logic can also be applied with pRight and lessFromRight to give the following code:\n```\n//define base cases for left of leftmost and right of rightmost.\nlessFromLeft[0] = -1;\nlessFromRight[nums.length-1] = nums.length;\n\n/*\nStart from left on lessFromLeft and right on lessFromRight as\nlessFromLeft[i] relies on values < i \nlessFromRight[i] relies on values > i.\n*/\n\nint left = 1;\nint right = nums.length-2;\n\n//loops through all min values on right and left.\nwhile(right >= 0) {\n    int pLeft= left-1;\n    while(pLeft >= 0 && nums[pLeft] >= nums[left]) {\n        pLeft = lessFromLeft[pLeft];\n    }\n\n    lessFromLeft[left] = pLeft;\n\n    int pRight = right+1;\n    while(pRight < nums.length && nums[pRight] >= nums[right]) {\n        sumRight[right] += (long)nums[pRight] + sumRight[pRight];\n        pRight = lessFromRight[pRight];\n    }\n    lessFromRight[right] = pRight;\n\n    left++;\n    right--;\n}\n\n```\n\nFinally, with the n subarrays calculated, iterate through all of them and find the one with the maximum min-product.\n\n```\nlong maxMinProduct = 0;\n\nfor(int i = 0; i < nums.length; i++) {\n    long sum = 0;\n    //sums the exclusive subarr (lessFromLeft[i], lessFromRight[i])\n    for(int j = lessFromLeft[i]+1; j < lessFromRight[i]; j++) {\n        sum += nums[j];\n    }\n    //multiplies sum  min nums[i] and checks against current max\n    maxMinProduct = Math.max(maxMinProduct, sum * nums[i]);\n}\nreturn (int)(maxMinProduct % mod);\n\n```\nHowever, this sum calculation itself is very inefficient as it has to sum every single number the subarray just like the original method for calculating lessFrom arrays had to iterate through each element individually. It would be more efficient to instead use an approach similar to our previous optimization of lessFrom while calculating the sum.\n\nTo accomplish this, we can can create the following arrays: \n```\nlong[] sumLeft = new long[nums.length];\nlong[] sumRight = new long[nums.length];\n```\nNote: due to the problems parameters, all sums must be longs to avoid Integer Overflow.\n\nThese both work as sort of prefix/suffix sums, where the arrays hold the sum of all the values to the left and to the right of index i for a subarray with i as its selected minimum position.\n\nThus, we can update the code from earlier that calculates the subarrays for each min to calculate these sums alongside it by adding every pLeft and pRight traversed, but also adding all the elements skipped by pLeft and pRight at once through adding sumLeft[pLeft] or sumRight[pRight].\n\n```\nint[] lessFromLeft = new int[nums.length];\nint[] lessFromRight = new int[nums.length];\nlong[] sumLeft = new long[nums.length];\nlong[] sumRight = new long[nums.length];\nlessFromLeft[0] = -1;\nlessFromRight[nums.length-1] = nums.length;\nint left = 1;\nint right = nums.length-2;\n\nwhile(right >= 0) {\n    int pLeft= left-1;\n    while(pLeft >= 0 && nums[pLeft] >= nums[left]) {\n        //adds current element and elements skipped to sum\n        sumLeft[left] += (long)nums[pLeft] + sumLeft[pLeft];\n        pLeft = lessFromLeft[pLeft];\n    }\n\n    lessFromLeft[left] = pLeft;\n\n    int pRight = right+1;\n    while(pRight < nums.length && nums[pRight] >= nums[right]) {\n        //adds current element and elements skipped to sum\n        sumRight[right] += (long)nums[pRight] + sumRight[pRight];\n        pRight = lessFromRight[pRight];\n    }\n    lessFromRight[right] = pRight;\n\n    left++;\n    right--;\n}\n```\nWith this optimized calculation, when doing the final min-product checks, each can be calculated in O(1) time as the sum for min position = i will be `nums[i] + sumLeft[i] + sumRight[i]`, with the min product simply being that sum*nums[i].\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n# Code\n```\nclass Solution {\n    int mod = (int)1e9 + 7;\n    public int maxSumMinProduct(int[] nums) {\n        int[] lessFromLeft = new int[nums.length];\n        int[] lessFromRight = new int[nums.length];\n        long[] sumLeft = new long[nums.length];\n        long[] sumRight = new long[nums.length];\n        lessFromLeft[0] = -1;\n        lessFromRight[nums.length-1] = nums.length;\n        int left = 1;\n        int right = nums.length-2;\n\n        while(right >= 0) {\n            int pLeft= left-1;\n            while(pLeft >= 0 && nums[pLeft] >= nums[left]) {\n                sumLeft[left] += (long)nums[pLeft] + sumLeft[pLeft];\n                pLeft = lessFromLeft[pLeft];\n            }\n\n            lessFromLeft[left] = pLeft;\n\n            int pRight = right+1;\n            while(pRight < nums.length && nums[pRight] >= nums[right]) {\n                sumRight[right] += (long)nums[pRight] + sumRight[pRight];\n                pRight = lessFromRight[pRight];\n            }\n            lessFromRight[right] = pRight;\n\n            left++;\n            right--;\n        }\n        long maxMinProduct = 0;\n        \n        for(int i = 0; i < nums.length; i++) {\n            long sum = nums[i] + sumLeft[i] + sumRight[i];\n            \n            maxMinProduct = Math.max(maxMinProduct, sum * nums[i]);\n        }\n        return (int)(maxMinProduct % mod);\n    }\n}\n```
['Array', 'Dynamic Programming', 'Prefix Sum', 'Java']