โปรแกรมหาขนาดสับลิสต์ที่ (min × size) สูงสุดและรวม index pos ใน Python

คำอธิบายโจทย์

ให้ nums และ pos หา subarray A ที่รวม index pos ทำให้ (min(A) × len(A)) สูงสุด

ตัวอย่าง

nums = [-2, 2, 5, 4], pos = 3 → 8 (subarray [5,4] min=4, size=2, 4×2=8)

วิธีแก้ปัญหา

Two Pointers Expand from Center:

1. เริ่ม i=j=pos, m = A[pos], ans = A[pos]
2. ขยายซ้ายหรือขวา ทีละขั้น เลือกด้านที่ค่ามากกว่า (greedy)
3. อัปเดต m = min(m, ค่าใหม่), ans = max(ans, m × (j-i+1))
4. ทำซ้ำ n-1 รอบ (ขยายจนครอบคลุมทั้งอาเรย์)

โค้ด Python

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))

อินพุต

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

เอาต์พุต

8