given an array of nonnegative integers representing an elevation map where the width of each bar is 1 this program calculates how much rainwater can be trapped example height 0 1 0 2 1 0 1 3 2 1 2 1 output 6 this problem can be solved using the concept of dynamic programming we calculate the maximum height of bars on the left and right of every bar in array then iterate over the width of structure and at each index the amount of water that will be stored is equal to minimum of maximum height of bars on both sides minus height of bar at current position the trappedrainwater function calculates the total amount of rainwater that can be trapped given an array of bar heights it uses a dynamic programming approach determining the maximum height of bars on both sides for each bar and then computing the trapped water above each bar the function returns the total trapped water trappedrainwater0 1 0 2 1 0 1 3 2 1 2 1 6 trappedrainwater7 1 5 3 6 4 9 trappedrainwater7 1 5 3 6 1 traceback most recent call last valueerror no height can be negative the trapped_rainwater function calculates the total amount of rainwater that can be trapped given an array of bar heights it uses a dynamic programming approach determining the maximum height of bars on both sides for each bar and then computing the trapped water above each bar the function returns the total trapped water trapped_rainwater 0 1 0 2 1 0 1 3 2 1 2 1 6 trapped_rainwater 7 1 5 3 6 4 9 trapped_rainwater 7 1 5 3 6 1 traceback most recent call last valueerror no height can be negative
def trapped_rainwater(heights: tuple[int, ...]) -> int:
    
    if not heights:
        return 0
    if any(h < 0 for h in heights):
        raise ValueError("No height can be negative")
    length = len(heights)

    left_max = [0] * length
    left_max[0] = heights[0]
    for i, height in enumerate(heights[1:], start=1):
        left_max[i] = max(height, left_max[i - 1])

    right_max = [0] * length
    right_max[-1] = heights[-1]
    for i in range(length - 2, -1, -1):
        right_max[i] = max(heights[i], right_max[i + 1])

    return sum(
        min(left, right) - height
        for left, right, height in zip(left_max, right_max, heights)
    )


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(f"{trapped_rainwater((0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)) = }")
    print(f"{trapped_rainwater((7, 1, 5, 3, 6, 4)) = }")