python - Find the largest sum of the maximal, compatible, values of two sorted arrays in sub quadratic time -

python - Find the largest sum of the maximal, compatible, values of two sorted arrays in sub quadratic time -

say have 2 sorted lists so:

a = [13, 7, 5, 3, 2, ..., 0] b = [16, 12, 8, 4, ..., 1]

also have function:

isvalid(x,y):

which returns true if x , y compatible. compatibility arbitrary, except value 0 valid other number.

so how find 2 numbers in , b such yield greatest sum given both isvalid. ie find greatest valid sum.

here current alg in python

def findbest(a, b): isdone = false achecked =[] bchecked = [] apossible = [] aindex = 0 bpossible = [] bindex = 0 posresult = [] #initialize try: apossible= (a[aindex]) aindex+=1 bpossible=(b[bindex]) bindex+=1 except: print "why did run on empty list?" homecoming while not isdone: posresult = [] if(len(apossible)>0): b in bchecked: if(isvalid(apossible,b)): posresult.append(apossible+b) isdone = true if len(bpossible)>0: in achecked: if(isvalid(a,bpossible)): posresult.append(a+bpossible) isdone = true #compare first 2 possibles if(isvalid(apossible,bpossible)): posresult.append(apossible+bpossible) isdone = true if(len(apossible) > 0): achecked.append(bpossible) if(len(bpossible) >0): bchecked.append(bpossible) if(aindex<len(a)): apossible= (a[aindex]) aindex+=1 if(bindex<len(b)): bpossible =(b[bindex]) bindex+=1 if len(a)==len(achecked) , len(b) == len(bchecked): print "none found" isdone = true homecoming posresult

but others has pointed out, worst case of o(n*n) n size of each list.

for worst case example, consider a = [9,8,7,0] , b = [4,3,2,1] there no compatible pairs other (0,4),(0,3),(0,2),(0,1).

let's optimistically assume somehow checked , found these 4 pair first. remembered pair (0,4) current-best answer. still need check pairs larger size 4 create sure (0,4) best answer. list pairs:

(9,4) (9,3) (8,4) (9,2) (8,3) (7,4) (9,1) (8,2) (7,3)

and number of these pairs growing o(n*n).

so impossible deduce sub quadratic time algorithm. [because assume best algorithm can implemented, algorithm still takes @ to the lowest degree o(n*n) on cases]

maybe left out more info question?

python algorithm sorting