Li Chao Query Value

Problem

Query the maximum value over a set of lines at a given x.

Given lines as [slope, intercept] pairs, return the largest slope * x + intercept. This is the value a Li Chao tree returns for its stored segment set.

Hint

A Li Chao tree answers maximum queries by descending to the best line at x.

Test cases

case 1

in: [[[1,0],[0,2]],3]

expected: 3

case 2

in: [[[-1,5],[1,-2]],0]

expected: 5

case 3

in: [[[2,1]],4]

expected: 9

Starter codePython

def li_chao_value(lines, x):
    # Your code here
    pass

3 test cases · run your code against them in the editor