playinwithfire's blog

unable to solve this question, need help
By playinwithfire, history, 13 months ago, In English

You have two arrays A and B. They have the same length and values are from positive integers. For example:

A = [6, 3, 4, 8, 3] B = [2, 4, 2, 1, 2]

You need to find such two indexes i, j where i != j such that expression A[i] * B[i] + A[i] * B[j] + A[j] * B[j] is maximized. For example here it is i = 3, j = 1 which gives maximum of 52

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I will assume that $$$i < j$$$ in this explanation. The other case is symmetric, so I will not explain it.

Now we go and process indices $$$j$$$ from first to last. For each index, we will find the optimal i and calculate the value of the function. How do we find the optimal $$$i$$$ though?

For all indices $$$i$$$ ($$$1 \le i < j$$$) we will put a function $$$f_i(x) = A_i \cdot x + A_i \cdot B_i$$$ in some container. Now values of picking current $$$j$$$ and some $$$i$$$ is $$$f_i(B_j) + A_j \cdot B_j$$$. As the second part is constant, we are only interested in finding the function with maximal value. Then we evaluate the expression, update our maximum, add function $$$f_j(x) = A_j \cdot x + B_j \cdot A_j$$$ into the container, and move on to the next $$$j$$$.

Now you might wonder how you add functions and find the maximal value fast. Well, you can use Li Chao Tree.

Time complexity is $$$O(N log N)$$$.

Not sure if there is a simpler way than using Li Chao, but this is the first solution that comes to my mind.

→ Reply