given array A, form array M such that sum of products (a1*m1+...+an*mn) is maximum

Question

I gave an interview recently where I was asked the following algorithmic question. I am not able to come to an O(n) solution nor I was able to find the problem doing google.

Given an array A[a_0 ... a_(n-1)] of integers (+ve and -ve). Form an array M[m_0 ... m_(n-1)] where m_0 = 2 and m_i in [2,...,m_(i-1)+1] such that sum of products is maximum i.e. we have to maximize a_0*m_0 + a_1*m_1 + ... + a_(n-1)*m_(n-1)

Examples

input  {1,2,3,-50,4}
output {2,3,4,2,3}

input  {1,-1,8,12}
output {2,3,4,5}

My O(n^2) solution was to start with m_0=2 and keep on incrementing by 1 as long as a_i is +ve. If a_i < 0 we have to consider all m_i from 2 to m_i-1 + 1 and see which one produces max sum of products.

Please suggest a linear time algorithm.

Answer 1

Suppose you have the following array:

1, 1, 2, -50, -3, -4, 6, 7, 8.

At each entry, we can either continue with our incrementing progression or reset the value to a lower value.
Here there can be only two good options. Either we would choose the maximum possible value for the current entry or the minimum possible(2). (proof towards the end)

Now it is clear that 1st 3 entries in our output shall be 2, 3 and 4 (because all the numbers so far are positive and there is no reason to reset them to 2 (a low value).

When a negative entry is encountered, compute the sum:
-(50 + 3 + 4) = -57.

Next compute the similar sum for succeeding +ve contiguous numbers.
(6 + 7 + 8) = 21.

Since 57 is greater than 21, it makes sense to reset the 4th entry to 2.

Again compute the sum for negative entries:
-(3 + 4) = -7.

Now 7 is less than 21, hence it makes sense not to reset any further because maximum product shall be obtained if positive values are high.

The output array thus shall be:

2, 3, 4, 2, 3, 4, 5, 6, 7

To make this algorithm work in linear time, you can pre-compute the array of sums that shall be required in computations.

Proof:

When a negative number is encountered, then we can either reset the output value to low value (say j) or continue with our increment (say i).

Say there are k -ve values and m succeeding positive values.

If we reset the value to j, then the value of product for these k -ve values and m +ve values shall be equal to:

- ( (j-2+2)*a1 + (j-2+3)*a2 + ... + (j-2+k+1)*ak ) + ( (j-2+k+2)*b1 + (j-2+k+3)*b2 + ... + (j-2+k+m+1)*am )

If we do not reset the value to 2, then the value of product for these k -ve values and m +ve values shall be equal to:

- ( (i+2)*a1 + (i+3)*a2 + (i+4)*a3 ... + (i+k+1)*ak ) + ( (i+k+2)*b1 + (i+k+3)*b2 + ... + (i+k+m+1)*am )

Hence the difference between the above two expressions is:

(i-j+2)* ( sum of positive values - sum of negative values )

Either this number can be positive or negative. Hence we shall tend to make j either as high as possible (M[i-1]+1) or as low as possible (2).

Pre-computing array of sums in O(N) time

Edited: As pointed out by Evgeny Kluev

1. Traverse the array backwards.
2. If a negative element is encountered, ignore it.
3. If a positive number is encountered, make suffix sum equal to that value.
4. Keep adding the value of elements to the sum till it remains positive.
5. Once the sum becomes < 0, note this point. This is the point that separates our decision of resetting to 2 and continuing with increment.
6. Ignore all negative values again till you reach a positive value.
7. Keep repeating till end of array is reached.

Note: While computing the suffix sum, if we encounter a zero value, then there can be multiple such solutions.