Chương trình tìm min-product lớn nhất của subarray trong Python

Cho mảng nums. Min-product của mảng = min(arrays) * sum(array). Tìm max min-product của mọi subarray không rỗng. Trả về modulo 10⁹+7.

Ví dụ: nums = [2,3,4,3] → output = 30 (subarray [3,4,3], min=3, sum=10, 3*10=30).

Giải thuật (Monotonic Stack + Prefix Sum)

• Duyệt mảng, dùng stack lưu (index, prefix_sum) tăng dần theo giá trị nums.
• Khi nums[i] ≤ nums[stack.top]: pop, tính area = nums[popped_index] * (current_prefix - prefix_before_popped).
• Cập nhật max. Push (i, current_prefix).
• Thêm sentinel 0 cuối mảng để flush stack.

Code Python

def solve(nums):
    m = int(1e9 + 7)
    stack = []
    rsum = 0
    res = 0
    nums.append(0)
    for i, v in enumerate(nums):
        while stack and nums[stack[-1][0]] >= v:
            index, _ = stack.pop()
            arrSum = rsum
            if stack:
                arrSum = rsum - stack[-1][1]
            res = max(res, nums[index] * arrSum)
        rsum += v
        stack.append((i, rsum))
    return res % m

nums = [2, 3, 4, 3]
print(solve(nums))  # 30

Đầu vào / Đầu ra

Input: [2,3,4,3]
Output: 30