โปรแกรมหาคะแนนสูงสุดของ Good Subarray ใน Python

ปัญหา

อาร์เรย์ nums และค่า k Score ของ Subarray (i,j) = min(nums[i..j]) × (j-i+1) Good Subarray: i ≤ k ≤ j หา Max Score

ตัวอย่าง

nums = [2,5,4,8,5,6], k = 3 → Output: 20

Optimal: (1,5) Min=4, Length=5 → 4×5=20

อัลกอริทึม (Two Pointers Expand from k)

1. เริ่มจาก i=j=k, minNum = nums[k], ans = nums[k]
2. ขยาย i ไปซ้าย, j ไปขวา ขณะที่ค่า ≥ minNum
3. อัปเดต Ans = max(Ans, (j-i-1) × minNum)
4. อัปเดต minNum = Max ของค่าที่หยุดอยู่ (Next Candidate)
5. ทำซ้ำจนครอบคลุมทั้งอาร์เรย์

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

def solve(nums, k):
    ans = nums[k]
    minNum = nums[k]
    i = j = k
    
    while i > -1 or j < len(nums):
        while i > -1 and nums[i] >= minNum:
            i -= 1
        while j < len(nums) and nums[j] >= minNum:
            j += 1
        ans = max(ans, (j - i - 1) * minNum)
        minNum = max(nums[i] if i > -1 else -1, nums[j] if j < len(nums) else -1)
    
    return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))  # 20

ความซับซ้อน

• Time: O(n) - แต่ละ Index ถูก Visit สูงสุด 1 ครั้ง
• Space: O(1)

คล้าย Largest Rectangle in Histogram แต่ขยายจาก k