Suppose we want to calculate max({A * a[i] + B * a[i + 1], A * a[i + 1] + B * a[i]}) for i = 0..n-1 (in this problem A = 0, B = 1). Then answer(A, B, n) = max(answer(max(A, B), A + B, n/2), A * a[n - 1] + B * a[n], B * a[n - 1] + A * a[n]), so it can be solved recursively.

That's very clever!
How did you come up with this idea?

It's been 2.5 years, so I don't remember clearly, but as far as I remember, I tried expanding formulas to find a simple formula for max. I didn't find such a formula, but I noted that the problem can be parametrized and expanded formulas fit that parametrization well.