5
$\begingroup$

Consider the following problem:

Given an array of $n$ integer numbers (positive and negative), find a (contiguous) subarray for which the product $(\text{sum of the elements})\times(\text{length of the subarray})$ is maximum.

Is there an algorithm with complexity less than $O(n^2)$?

For instance, if the array is $$-2,\ 3,\ 7,\ -8,\ -15,\ \underline{1,\ 1,\ 7,\ -2},\ -3$$ then the underlined subarray would be the one we are looking for (its "score" is 7×4 = 28).

I tried everything I know (dynamic programming, greedy, divide and conquer, the general "fix one endpoint and find the other"), and asked many people, but nobody could find an answer.

$\endgroup$
  • $\begingroup$ @D.W. Can you implement dynamic programming faster than $O(n^2)$? $\endgroup$ – Yuval Filmus Jun 16 '14 at 2:35
  • $\begingroup$ Check out the solution to the largest sum contiguous subarray problem, I'm pretty sure it can be adapted for your case. $\endgroup$ – vonbrand Jun 16 '14 at 3:02
  • $\begingroup$ @D.W. I tried everything I know (dp, greedy, divide and conquer, the general "fix one endpoint and find the other"), and asked many people, but nobody could find an answer. I posted it here hoping to find someone more expert on algorithms than I am. This is no homework, and as far as I know this problem may be an open problem. You seem to think there is a simple sub-quadratic solution using dp, if so please share with us. $\endgroup$ – obag Jun 16 '14 at 11:57
  • $\begingroup$ obag, I don't know of a dynamic programming solution faster than $O(n^2)$. I just wanted to know what you have already tried (normally we expect you to give us some idea of that). Also, it's often helpful to let us know the context where you ran across this or the motivation/application; and if you have some reason to believe it is possible to solve this faster than $O(n^2)$ time, please let us know what that is. $\endgroup$ – D.W. Jun 16 '14 at 19:54
  • $\begingroup$ D.W., The motivation for the problem comes from the fact that if you change (length × sum) into (length × min) or (length × gcd) there is a simple sub-quadratic solution (I can elaborate, but the approach used there is not applicable here). I was curious to know whether there was a way to solve the length × sum problem as well. $\endgroup$ – obag Jun 17 '14 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.