I was working on a different problem and I would need to solve this as a subproblem in faster than $$$O(n^2)$$$ to solve the actual problem.

Statement

You are given 2 arrays $$$a_{0}, a_{1}, ..., a_{n-1}$$$ and $$$b_{0}, b_{1}, ..., b_{n-1}$$$, both increasing i.e. $$$\forall_{0 \leq i < n - 1}$$$ $$$a_{i} \leq a_{i+1}$$$ and $$$b_{i} \leq b_{i+1}$$$ and also $$$\forall_{i} a_{i} \geq 0, b_{i} \geq 0$$$. You task is to find array $$$c$$$ such that:

$$$c_i = max_{0 \leq j < 2 * n} a_{j} + b_{i-j}.$$$

For example, for $$$a = [2, 3, 5, 8]$$$ and $$$b = [1, 4, 7, 8]$$$, the result would be $$$c = [3, 6, 9, 10, 12, 15, 16]$$$.

So the simple code to solve this is:

for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    c[i + j] = max(c[i + j], a[i] + b[j]);
  }
}

Tried approach

I had a few ideas of attacking this by drawing out the full matrix of sums of $$$a$$$ x $$$b$$$ and trying to notice that the $$$c_{i}$$$'s will form a path within this matrix from the top-left to lower-right corner, but I wasn't able to complete this. Is there a better solution than the proposed brute-force solution?