Chương trình tìm kích thước dãy con mà tích min(A) * size(A) lớn nhất trong Python

Cho danh sách nums và vị trí pos. Tìm dãy con A chứa index pos sao cho (min(A) * len(A)) lớn nhất.

Ví dụ: nums = [-2, 2, 5, 4], pos = 3 → 8 (dãy [5,4], min=4, size=2, 4*2=8).

Giải pháp

Mở rộng hai con trỏ từ pos ra hai bên theo chiến lược greedy:

• Khởi tạo i=j=pos, m=ans=nums[pos]
• Lặp n-1 lần: so sánh left = A[i-1] và right = A[j+1] (coi -inf nếu ngoài mảng)
• Mở rộng về phía có giá trị lớn hơn (để giữ min lớn nhất có thể)
• Cập nhật m = min(m, phần tử mới), ans = max(ans, m * (j-i+1))

Ví dụ minh họa

class Solution:
    def solve(self, A, pos):
        NINF = float("-inf")
        ans = m = A[pos]
        i = pos
        j = pos
        for _ in range(len(A) - 1):
            left = A[i - 1] if i - 1 >= 0 else NINF
            right = A[j + 1] if j + 1 < len(A) else NINF
            if left >= right:
                i -= 1
                m = min(m, A[i])
            else:
                j += 1
                m = min(m, A[j])
            ans = max(ans, m * (j - i + 1))
        return ans

ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos))

Đầu vào

[-2, 2, 5, 4], 3

Đầu ra

8