โปรแกรมหาค่าสูงสุดของกลุ่มที่เล็กที่สุดเมื่อแบ่งอาเรย์ K กลุ่มใน Python

ตัวอย่าง

Input: nums = [2, 6, 4, 5, 8], k = 3

Output: 8

แบ่ง: [2,6]=8, [4,5]=9, [8]=8 → min sum = 8 (สูงสุดที่เป็นไปได้)

แนวทางแก้ปัญหา

Binary Search คำตอบ + Greedy Check:

1. Binary search target ในช่วง [1, sum(nums)//k + 1]
2. valid(target): วนสะสมผลรวม ถ้า ≥ target → นับกลุ่ม+1, reset sum → ถ้าทำได้ ≥ k กลุ่ม → True

การใช้งาน (Python)

class Solution:
    def solve(self, nums, k):
        def can_divide(target):
            if target <= 1:
                return True
            groups = 0
            cur = 0
            for x in nums:
                cur += x
                if cur >= target:
                    groups += 1
                    cur = 0
                    if groups == k:
                        return True
            return False
        
        left, right = 1, sum(nums) // k + 1
        while left < right - 1:
            mid = (left + right) // 2
            if can_divide(mid):
                left = mid
            else:
                right = mid
        return left

# ทดสอบ
ob = Solution()
print(ob.solve([2, 6, 4, 5, 8], 3))  # Output: 8

ความซับซ้อน

• Time Complexity: O(N log Sum)
• Space Complexity: O(1)

เป็นปัญหา "Split Array Largest Sum" แบบกลับกัน (maximize minimum)