LC 5752. 子数组最小乘积的最大值

https://leetcode-cn.com/problems/maximum-subarray-min-product/

这题的思路是，针对每个元素，假设这个元素是最小值，那么它所能覆盖的最大区间是什么。

这个寻找最大区间有点类似于构建find-union结构，我们以A[i]寻找最左侧点为例

  1. j = i - 1
  2. 假设A[i] > A[j]的话，那么最左侧点就是 j+1
  3. 如果A[i] <= A[j] 的话，那么最左侧点必然在 left[j] 更左侧
  4. j = left[j] - 1, 跳转到步骤2继续寻找

这个时间复杂度不太好确认，但是方法上似乎和find-union结构相近，并且有路径压缩，所以猜想时间复杂度是反ack函数 https://en.wikipedia.org/wiki/Ackermann_function#Inverse 

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        left = [-1] * n
        right = [-1] * n
        left[0] = 0
        right[-1] = n - 1

        for i in range(1, n):
            x = nums[i]
            j = i - 1
            while j >= 0 and x <= nums[j]:
                j = left[j] - 1
            left[i] = j + 1

        for i in reversed(range(n - 1)):
            x = nums[i]
            j = i + 1
            while j < n and x <= nums[j]:
                j = right[j] + 1
            right[i] = j - 1

        acc = [0] * (n + 1)
        for i in range(n):
            acc[i + 1] = nums[i]
        for i in range(n):
            acc[i + 1] += acc[i]

        left[0] = 0
        right[-1] = n - 1
        ans = 0
        for i in range(n):
            l, r = left[i], right[i]
            x = nums[i]
            acc2 = acc[r + 1] - acc[l]
            m = x * acc2
            ans = max(ans, m)
            # print(m)

        MOD = 10 ** 9 + 7
        return ans % MOD