You are given n <= 1e6 numbers, all a[i] <= 1e6, among all pairs of indices (i, j), such that i != j you need to find the maximum value of (a[i] + a[j]) * (j — i). Only one solution involving something similar to D&C DP optimization is known to me, are there any others?