Tima10's blog

Find maximal possible value of (a[i] + a[j]) * (j — i)
By Tima10, history, 5 years ago, translation, In English

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?

  • Vote: I like it
  • +43
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it -23 Vote: I do not like it

We can use bit mask dp also. Note (a[I]+a[j])<= $$$2*10^6$$$. We can fix this value and find max value of (j-i).

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

This problem. You can either read koosaga's editorial or ICPC 2017 problem D editorial (same problem).

→ Reply