Prefix Sum உடன் Binary Search

Sum constraint-ஐப் பொறுத்து split / threshold / window length: prefix sums + binary search.

Try this in Python

def longest_subarray_sum_leq(nums: list[int], limit: int) -> int:
    """Find longest length L such that some subarray of length L has sum <= limit (illustrative)."""
    p = [0]
    for x in nums:
        p.append(p[-1] + x)

    def exists_len(L: int) -> bool:
        if L == 0:
            return True
        for i in range(L, len(p)):
            if p[i] - p[i - L] <= limit:
                return True
        return False

    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if exists_len(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo


print(longest_subarray_sum_leq([2, 1, 3, 4], 6))

Key takeaways

• இந்த exists_len readable; optimize பின்னர்.
• மெதுவாக இருந்தால் two-pointer.
• empty array சோதி.