Find maximal possible value of (a[i] + a[j]) * (j — i)

Revision en3, by Tima10, 2021-08-30 22:34:28

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 other solutions?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Tima10 2021-08-30 22:34:28 9 Tiny change: ' any others?\n\n' -> ' any other solutions?\n\n'
en2 English Tima10 2021-08-30 22:32:54 4 Tiny change: 'imilar to D&C DP optimizat' -> 'imilar to **D&C DP** optimizat'
en1 English Tima10 2021-08-26 19:18:30 346 Initial revision for English translation
ru2 Russian Tima10 2021-08-26 19:18:19 18
ru1 Russian Tima10 2021-08-26 13:46:31 330 Первая редакция (опубликовано)