Chương trình Python tìm tổng minimum của mọi sublist

Cho danh sách nums. Tính tổng minimum của mọi sublist (dãy con liên tiếp) của nums. Kết quả modulo 10^9 + 7.

Ví dụ

nums = [5, 10, 20, 10, 0]
Sublists: 15 cái
Minimums: [5,10,20,10,0, 5,10,10,0, 5,10,0, 5,0, 0]
Sum = 90

Thuật toán: Monotonic Stack + Contribution

Thay vì liệt kê O(n²) sublist, tính đóng góp của mỗi phần tử là minimum của bao nhiêu sublist.

• Dùng stack đơn điệu tăng lưu (index, value, contribution).
• Khi gặp value <= stack[-1].value: pop, trừ contribution cũ.
• Contribution mới = (i - prev_index) * value (số sublist kết thúc tại i mà value là min).
• Tích lũy temp_sum = tổng contribution của stack = tổng min của sublist kết thúc tại i.
• ans += temp_sum.

Code Python

def solve(nums):
    MOD = 10**9 + 7
    ans = 0
    stack = []  # (index, value, contribution)
    temp_sum = 0
    
    for i, val in enumerate(nums):
        # Pop các giá trị >= val (không còn là min)
        while stack and val <= stack[-1][1]:
            temp_sum -= stack[-1][2]
            stack.pop()
        
        # Tính contribution mới
        if not stack:
            contrib = (i + 1) * val
        else:
            contrib = (i - stack[-1][0]) * val
        
        stack.append([i, val, contrib])
        temp_sum += contrib
        ans += temp_sum
    
    return ans % MOD

# Test
print(solve([5, 10, 20, 10, 0]))  # 90
print(solve([3,1,2,4]))           # 17

Trace ví dụ [5, 10, 20, 10, 0]

i=0, val=5:  stack=[(0,5,5)], temp=5, ans=5
i=1, val=10: stack=[(0,5,5),(1,10,10)], temp=15, ans=20
i=2, val=20: stack=[(0,5,5),(1,10,10),(2,20,20)], temp=35, ans=55
i=3, val=10: pop 20(temp=15), pop 10(temp=5), push (3,10,30), temp=35, ans=90
i=4, val=0:  pop all, push (4,0,0), temp=0, ans=90

Độ phức tạp

• Thời gian: O(n) - mỗi phần tử push/pop tối đa 1 lần.
• Không gian: O(n) cho stack.

Kỹ thuật kinh điển: "Sum of Subarray Minimums" (LeetCode 907).