Binary Search Partition யோசனைகள்

k குழுக்களாக split — maximum sum-ஐ குறைக்க: maximum sum binary search; feasibility monotone எனில்.

Try this in Python

def split_array_minimize_largest_sum(nums: list[int], k: int) -> int:
    def can(limit: int) -> bool:
        parts, cur = 1, 0
        for x in nums:
            if cur + x <= limit:
                cur += x
            else:
                parts += 1
                cur = x
                if parts > k:
                    return False
        return True

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(split_array_minimize_largest_sum([7, 2, 5, 10, 8], 2))

Key takeaways

• minimize max pattern.
• check-இல் greedy packing.
• lo = max(nums) ஏன் என்பதைப் புரிந்து கொள்.