[Go] Monotonic Stack - explanation in comments
A monotonic stack is a stack that keeps an invariant. \nAn increasing monotonic stack, keeps the invariant that the items on the stack are in increasing order.\
A monotonic stack is a stack that keeps an invariant. \nAn **increasing** monotonic stack, keeps the invariant that the items on the stack are in increasing order.\nA **decreasing** monotonic stack, keeps the invariant that the items on the stack are in decreasing order.\n\n**key note:** we don\'t keep the values on the stack, we keep their indeces as long as the values at these indeces keep the invariant described above.\n\nWhat does the monotonic stack give us? It allows us to find the Next *increasing/decreasing* Element and the Previous *increasing/decreasing* Element. \n\n```\nfunc maxSumMinProduct(nums []int) int {\n    // maintain an increasing stack\n    // store indeces on the stack rather than actual values (important)\n    //          storing indeces provides us with a window\n    // the invariant on the stack is like this\n    //\n    //                ..... j-th item is the item we\'re on                           j\n    //                |     this is the END BORDER of our window                ....][....\n    //                |\n    //          [1,2] 1\n    //           |  \\___stack.Pop() is the *previous* minimum,                       j\n    //           |                  so its the previous windows minimum   .....m....][......\n    //            \\stack.Top() is the prev-previous minimum \n    //                         the minimum BEFORE the beginning          i           j\n    //                         of this window                       .....][....m....][......\n    //\n    // therefore the window we\'re looking at is between (i:j)  - exclusive \n    //                                     therefore [i+1:j-1] - inclusive\n    //\n    // the FORMULA becomes m * prefix_sum(i+1:j-1)\n    \n    // set up boundaries [-1] + [nums] + [-1]\n    nums = append([]int{-1}, append(nums, -1)...)\n    \n    prefix, stak := NewPrefixSum(nums), NewStack()\n    maxProd := 0\n    // i = start; j = end; m = curr\n    for end := range nums {\n        for stak.Len() > 0 && nums[end] < nums[stak.Top()] {\n            curr, start := stak.Pop(), stak.Top()\n            maxProd = max(maxProd, nums[curr] * prefix.Sum(start+1, end-1))\n        }\n\n        stak.Push(end)\n    }\n\n    return maxProd % (1e9+7)\n}\n\ntype pSum struct {\n    Sum   func(i, j int) int\n}\n\nfunc NewPrefixSum(arr []int) pSum {\n    // build the sums\n    sums := make([]int, len(arr) + 1)\n    for i:=0; i<len(arr); i++ { \n        sums[i+1] = sums[i] + arr[i]\n    }\n    return pSum{\n        Sum: func(i, j int) int {\n          return sums[j+1] - sums[i]  \n        },\n    }\n}\n\ntype stack struct {\n    Len     func() int\n    Push    func(x int)\n    Pop     func() int\n    Top     func() int\n    Print   func() string\n}\n\nfunc NewStack() stack {\n    arr := make([]int, 0)\n    return stack{\n        Len: func() int {\n            return len(arr)\n        },\n        Push: func(x int) {\n            arr = append(arr, x)\n        },\n        Pop:  func() int {\n            item := arr[len(arr)-1]\n            arr = arr[:len(arr)-1]\n            return item\n        },\n        Top: func() int {\n            return arr[len(arr)-1]\n        },\n        Print: func() string {\n            return fmt.Sprintf("%d", arr)\n        },\n    }\n}\n\nfunc max(x, y int) int {\n    if x > y {\n        return x\n    }\n    return y\n}\n```
['Monotonic Stack', 'Go']