Basically you want to compute the max convolution of two array in subquadratic time. I once spent like 3 hours searching for it and only found some recent articles mentioning that no prior results are known to solve it. I found at the time some probabilistic method (written by some Germans about 40 years ago) that worked in practice but failed really hard certain tests. My final answer would be: I'm 99% sure there is no known solution yet. There was some algorithm in N^1.8something (that worked only if the arrays met certain conditions and from what I've read in practice it worked as bad as N^2)

PS: Also, I find the post extremely useful because it took me a lot to find out what I just said about the problem, and it's also the kind of subproblem that may appear as part of solving other tasks that it'd be better to know if it is solvable or not

I see only that we can change ai+bk-i to 1,00000001^ai*1,00000001^bk-i and now it more similar to multiplication of polynomials.

Like geniucos has mentioned, this might be a bit of a challenging problem.

What are you trying to compute is called convolution in the "tropical semiring". You can find more on here: Link

My only idea would be to employ some kind of randomized algorithm with a good "success" rate.

What's range for a_i and b_i, 10^5 or 10^9