1856. Maximum Subarray Min Product - Explanation

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        res, MOD = 0, 1000000007
        for i in range(len(nums)):
            total_sum = 0
            mini = float("inf")
            for j in range(i, len(nums)):
                mini = min(mini, nums[j])
                total_sum += nums[j]
                cur = (mini * total_sum) % MOD
                res = max(res, cur)
        return res

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7

        def rec(l, r):
            if l > r:
                return 0

            min_idx = l
            total_sum = 0
            for i in range(l, r + 1):
                total_sum += nums[i]
                if nums[i] < nums[min_idx]:
                    min_idx = i

            cur = total_sum * nums[min_idx]
            left = rec(l, min_idx - 1)
            right = rec(min_idx + 1, r)

            return max(cur, left, right)

        return rec(0, len(nums) - 1) % MOD

class SegmentTree:
    def __init__(self, N, A):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.build(N, A)

    def build(self, N, A):
        self.tree = [(-1, float('inf'))] * (2 * self.n)
        for i in range(N):
            self.tree[self.n + i] = (i, A[i])
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = min(self.tree[i << 1], self.tree[i << 1 | 1], key=lambda x: x[1])

    def query(self, l, r):
        res = (-1, float('inf'))
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = min(res, self.tree[l], key=lambda x: x[1])
                l += 1
            if r & 1:
                r -= 1
                res = min(res, self.tree[r], key=lambda x: x[1])
            l >>= 1
            r >>= 1
        return res[0]

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        segTree = SegmentTree(len(nums), nums)
        prefix_sum = [0] * (len(nums) + 1)
        for i in range(0, len(nums)):
            prefix_sum[i + 1] += prefix_sum[i] + nums[i]

        def rec(l, r):
            if l > r:
                return 0

            min_idx = segTree.query(l, r)
            total_sum = prefix_sum[r + 1] - prefix_sum[l]
            cur = total_sum * nums[min_idx]
            left = rec(l, min_idx - 1)
            right = rec(min_idx + 1, r)

            return max(cur, left, right)

        return rec(0, len(nums) - 1) % MOD

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        prev_min, nxt_min = [-1] * n, [n] * n
        stack = []

        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                prev_min[i] = stack[-1]
            stack.append(i)

        stack.clear()

        for i in range(n - 1, -1, -1):
            while stack and nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                nxt_min[i] = stack[-1]
            stack.append(i)

        res = 0

        for i in range(n):
            l, r = prev_min[i] + 1, nxt_min[i] - 1
            total_sum = prefix_sum[r + 1] - prefix_sum[l]
            res = max(res, nums[i] * total_sum)

        return res % (10 ** 9 + 7)

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        res = 0
        stack = []

        for i, num in enumerate(nums):
            new_start = i
            while stack and stack[-1][1] > num:
                start, val = stack.pop()
                total = prefix[i] - prefix[start]
                res = max(res, val * total)
                new_start = start
            stack.append((new_start, num))

        while stack:
            start, val = stack.pop()
            total = prefix[n] - prefix[start]
            res = max(res, val * total)

        return res % (10**9 + 7)

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        n = len(nums)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]

        res, stack = 0, []
        for i in range(n + 1):
            while stack and (i == n or nums[i] < nums[stack[-1]]):
                j = stack.pop()
                start = 0 if not stack else stack[-1] + 1
                res = max(res, nums[j] * (prefix_sum[i] - prefix_sum[start]))
            stack.append(i)

        return res % (10 ** 9 + 7)