โปรแกรมหา Maximum Subarray Min-Product ใน Python

ปัญหา

อาร์เรย์ nums หา Max Min-Product ของทุก Non-empty Subarray Min-Product = Min(Subarray) × Sum(Subarray) Mod 10^9+7

ตัวอย่าง

nums = [2,3,4,3] → Output: 30

Subarray [3,4,3]: Min=3, Sum=10 → 3×10=30

อัลกอริทึม (Monotonic Stack + Prefix Sum)

1. Append 0 ท้าย nums (Sentinel)
2. Monotonic Increasing Stack เก็บ (Index, Prefix_Sum_Upto_Index)
3. เมื่อเจอค่าที่ ≤ Stack Top: Pop คำนวณ Area = Height × (Current_Prefix - Previous_Prefix)
4. คล้าย Largest Rectangle in Histogram แต่ Height = nums[i], Width = Sum of Elements

ตัวอย่างโค้ด

def solve(nums):
    m = int(1e9 + 7)
    stack = []
    rsum = 0
    res = 0
    nums.append(0)  # Sentinel
    
    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

ความซับซ้อน

• Time: O(n)
• Space: O(n)

แต่ละ Element Push/Pop Stack สูงสุด 1 ครั้ง