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 74 = 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. 
Subarray whose (sum  length) is maximum
algorithms;subsequences;maximum subarray