def rod_cutting(price_table):
    """
    price_table: list where price[i] is price of rod of length i
           (price[0] is expected to be 0)
    """
    n = len(price_table)-1   # Length of the rod - excluding zeroth element
    # r[j] will store maximum revenue for rod of length j
    r = [0] * (n + 1)

    for j in range(1, n + 1):
        q = -1
        for i in range(1, j + 1):
            q = max(q, price[i] + r[j - i])
        r[j] = q

    return r[n]




# Price table. price[0] should be zero
price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

max_revenue = rod_cutting(price)
print("Maximum Revenue:", max_revenue)
