[Python] Disjoint Set Union, iterate from largest to smallest
This is a intuition of the process\n- We iterate from the largest number to the smallest number.\n- At every iteration, if the adjacent number(s) is larger than
This is a intuition of the process\n- We iterate from the largest number to the smallest number.\n- At every iteration, if the adjacent number(s) is larger than the current number, merge it with the adjacent group(s).\n- After every merge, we update the sum of the group and the minimum value of the group. We update the result if applicable.\n\nWe use a disjoint set union to track the group membership. You can get the disjoint set union template from elsewhere.\n\nWe use another dictionary to track the current sum of each group.\n\n```python\nclass DisjointSet:\n    # github.com/not522/ac-library-python/blob/master/atcoder/dsu.py\n\n    def __init__(self, n: int = 0) -> None:\n        self._n = n\n        self.parent_or_size = [-1]*n\n\n    def union(self, a: int, b: int) -> int:\n        x = self.find(a)\n        y = self.find(b)\n\n        if x == y:\n            return x\n\n        if -self.parent_or_size[x] < -self.parent_or_size[y]:\n            x, y = y, x\n\n        self.parent_or_size[x] += self.parent_or_size[y]\n        self.parent_or_size[y] = x\n\n        return x\n\n    def find(self, a: int) -> int:\n        parent = self.parent_or_size[a]\n        while parent >= 0:\n            if self.parent_or_size[parent] < 0:\n                return parent\n            self.parent_or_size[a], a, parent = (\n                self.parent_or_size[parent],\n                self.parent_or_size[parent],\n                self.parent_or_size[self.parent_or_size[parent]]\n            )\n\n        return a\n\n    def size(self, a: int) -> int:\n        return -self.parent_or_size[self.leader(a)]\n\n\nclass Solution:\n    def maxSumMinProduct(self, nums: List[int]) -> int:\n        \n        # we begin from the largest number to the smallest number\n        nums = [0] + nums + [0]\n        pos = [(x,i) for i,x in enumerate(nums)]\n        pos.sort()\n        pos.reverse()\n        \n        # we track the result with this variable\n        maxres = 0\n        \n        # we track the membership of each element\n        # d.find(x) == d.find(y) if x and y are in the same group\n        d = DisjointSet(len(nums))\n\n        # we track the current sum of each group with a dictionary\n        # map group_id (which may change over time) to the sum\n        segsums = {}\n        \n        # iterate from the largest to the smallest number and index\n        # excluding the two zeros padded at the ends\n        for x,i in pos[:-2]:\n            minval = x  # current value is minimum since we iterate from large to small\n            segsum = x\n            \n            # if the left element is larger\n            if nums[i-1] > nums[i]:     \n                idx = d.find(i-1)       # get group index\n                segsum += segsums[idx]  # include sum of adjacent group\n                d.union(i, i-1)         # combine groups\n            \n            # equality because we iterate with decreasing index as well\n            if nums[i+1] >= nums[i]:\n                idx = d.find(i+1)\n                segsum += segsums[idx]\n                d.union(i, i+1)\n            \n            # update sum of group\n            segsums[d.find(i)] = segsum  \n            \n            # update the result\n            maxres = max(maxres, minval*segsum)\n        \n        # remember to take modulo\n        return maxres%(10**9+7)\n```\n\nThe algorithm runs in O(n log n) due to the sorting.
['Python3']