I think many have thought of this before, and there exists no algorithm better than $$$O(n^2)$$$. However, you may find this interesting.

Edit: Found the source for my claim: here.

I found this.

$$$\mathcal{O} \left(\frac{n^2 (\log \log n)^3}{\log^2 n}\right)$$$ seems really scary.

Isn’t this just knapsack? It’s highly unlikely to have better complexity than quadratic, because if you cpuld, you would solve knapsack better than quadratically.

There are some reductions to and from this problem, so existence of truly-subquadratic algorithm for it is quite unlikely.

There is a nice paper describing most of the recent results related to this problem including reductions to this problem, approximate, parametrized and $$$o(n^2)$$$ (but not $$$O(n^{2-\epsilon})$$$) algorithms for it.

I am quite sure this problem (or a very similar one) was posed on some old Codeforces round as Div1B for n<=1e5 with guarantee that input sequence is random in some way. However I don't remember any keywords, so I don't know how to search for it.

EDIT: OK, it turns out it took me half a minute to find it xD https://codeforces.me/problemset/problem/444/B?locale=en There is product there and one of the sequences is zero-one.

If we have special property called "concavity" on both array $$$a$$$ and $$$b$$$, we can solve it in $$$O(n)$$$. For array $$$v = (v_1, v_2, ..., v_n)$$$, the array $$$v$$$ is concave if $$$v_i - v_{i+1}$$$ is decreasing.

That's because (if concavity holds), when $$$c_k$$$ is selected from $$$a_i + b_j$$$, the value of $$$c_{k+1}$$$ is the larger value of $$$a_{i+1} + b_j$$$ and $$$a_i + b_{j+1}$$$. We can choose it greedily.

There are many problems which uses this technique, even in competitive programming.